Question

数据结构题目

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表
(C) 双链表 (D) 仅有尾指针的单循环链表
选哪项？为什么？

Answer 1

时间问题，明天把五题补上，或者发到你邮箱里

一，

1 D 数据元素是数据的基本单位, 数据项是不可分割的最小单位。

2 C 线性表是由类型相同的数据元素组成的有限序列。线性表的数据元素可以是最简的数值和字符，也可以是比较复杂的信息。

4 B 根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“象”作为记录在表中的存 储位置，这种表便成为哈希表。哈希函数是一个映像，因此哈希函数的设定很灵活，不需进行比较就可以直接取得所查记录。

5 C 根据二维数组A[u1][u2]的列优先映射所对应的映射函数 map(i1，i2) = i2 * u1 + i1 其中u1=8 u2=10 ; i1=3 i2=6 ; map=6*8+3=51
即4000+51*2=4102

6 D 根据后进先出原则c/d/a/b：c进栈然后出栈；a,b,d先后进栈，d出栈；此时栈中有a,b两个元素，必须是b先出栈，所以不会出现c/d/a/b序列

二，1 数据的存储结构（即物理结构） 2、线性表中数据元素的个数n称为线性表的长度。 3 后进先出

4、2056；2086。。u1=10，u2=8；i1=4-1=3，i2=5-1=4 ；行优先：map(i1，i2) = i1 * u2 + i2=28；列优先：map(i1，i2) = i2 * u1 + i1 =43

5 一个算法应该具有以下特点： 有穷性 、确定性、有零个或多个输入、有一个或多个输出、有效性 6、 n-i+1

三，1、当要求随机存取线性表的任一元素，且逻辑上相邻的元素在物理位置上也相邻时，要采用顺序结构。

因为线性表的顺序存储结构是用一组地址连续的存储单元依次存储线性表的元素，

用元素在存储器中的“物理位置相邻”表示线性表中数据元素之间的逻辑关系，可随机存取任一个数据元素，是一种随机存储结构。

2、当不要求逻辑上相邻的元素在物理位置上也相邻，不要求随机存取任一数据元素，但需要进行有效率的插入、删除等操作时，要采用链式存储 结构。（只讨论单链式）

因为线性表的链式存储结构中用结点中的指针域表示数据元素之间的逻辑关系，这样逻辑上相邻的两个元素部要求物理存储位置也相邻。

且每个元素的存储位置由其直接前驱的指针表示，方便进行插入、删除等操作，是一种非随机存储结构。

四，1、 A[1][0] - A[2][0] - A[1][1] - A[2][1] - A[1][2] - A[2][2] （自己画框框吧。。。）

2、。。。。这个就不用了吧 你肯定会的

五 1、//--------循环队列----队列的顺序存储结构----------
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType *base; // 初始化的动态分配存储空间
int front; //头指针，若队列不空，指向队列头元素
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
} Q ;

Status EnQueue (Q, x){ //插入元素x为新的队尾元素
if (( Q.rear +1)%MAXQSIZE = = Q.front ) return ERROR; // 队列满
Q.base[Q.rear] = x ;
Q.rear = (Q.rear+1)%MAXQSIZE ;
return OK ;
}

Status GetTop(Q, QElemType &e) { //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
if (Q.front = = Q.rear) return ERROR ; //队列为空 返回error
e = Q.base[Q.front];
Q.front = (Q.front +1 ) % MAXQSIZE ;
return OK;
}

2、一个带头结点的线性链表类型定义如下：
typedef struct LNode { // 结点类型
ElemType date ;
struct LNode *next ;
} *Link, *Position ;

typedef struct { //链表类型
Link head,tail ; //分别指向线性链表中的头结点和最后一个结点
int len ; //指示线性链表中数据元素的个数
} LinkList ；

Status Excha-L ( LinkList &L, int i) {

for(int i = n; i>=1; i--)
{ s = L[i-1]*next;
InsFirst(head,s) ； } // 已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
L[0]*next = tail ;
return OK ;
} // Excha-L

3、由于线性表的长度可变，在C语言中可用动态分配的一维数组，一般情况下，
删除第i（(1≤i≤n)个元素）时需将从i+1 至第n（共n-i）个元素依次向前移动一个位置。如下描述：

#define LIST-SIZE maxlen // 线性表存储空间的初始分配量
typedef struct {
ElemType *elem ; // 存储空间基址
int length ; // 当前长度
int listsize ; // 当前分配的存储容量
} Stlist ;

Status Listdelete-St (Stlist &L, int i ，ElemType &e) {
// 在顺序线性表L中删除第i个元素，并用e返回其值
// i的合法值为1≤i≤ListLength-St
if ((i<1) || (i> L.length)) return ERROR ; // i值不合法
p = & (L.elem[i-1]) ; //p为被删除元素的位置
e = *p ; //被删除元素的值赋给e
q = L.elem + L.length -1 ; //表尾元素的位置
for (++p; p<=q ; ++p) * (p-1) = *p ; //被删除元素之后的元素左移
- -L.length ; //表长减1
return OK ;
} // ListDelete - St
请参考