数据结构试卷及答案

7. 中序

8. 7 第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。

在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 9. O(1)

10. i/2，2i+1

11. (5，16，71，23，72，94，73) 12. (1，4，3，2)

13. j+1，hashtable[j].key==k 14. return(t)，t=t->rchild

1. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为[O(n2)]，快速排序的平均时间复杂度为[O(nlog2n)]。

2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为[p>llink->rlink=p->rlink]设结点中的两个指针域分别为llink和rlink）。 3. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为[3]。

4. 深度为k的完全二叉树中最少有[2k-1]个结点。

5. 设初始记录关键字序列为(K1，K2，?，Kn)，则用筛选法思想建堆必须从第[n/2]个元素开始进行筛选。 6. 设哈夫曼树中共有99个结点，则该树中有[50]个叶子结点；若采用二叉链表作为存储结构，则该树中有[51]个空指针域。 7. 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储[m-1]个队列元素；当前实际存储[(R-F+M)%M]个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

8. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中[n+1-i]个数据元素；删除第i个位置上的数据元素需要移动表中[n-i]个元素。

9. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为[(19，18，16，20，30，22)]。

10. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为[(16，18，19，20，32，22)]。 11. 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是[A[i][j]=1]。 12. 设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数[等于]第i列上非0元素的个数（填等于，大于或小于）。 13. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为[BDCA]。 14. 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。 typedef struct node {

int key;

struct node *next; } lklist;

void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i]; k=a[i] % p;

s->next=hashtable[k]; [hashtable[k]=s]; } }

1. O(n2)，O(nlog2n)

2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3 4. 2k-1 5. n/2 6. 7. 8. 9.

50，51

m-1，(R-F+M)%M n+1-i，n-i

(19，18，16，20，30，22)

10. (16，18，19，20，32，22) 11. A[i][j]=1

12. 等于 13. BDCA

14. hashtable[i]=0，hashtable[k]=s

1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是[top1+1=top2]。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是[可以随机访问到任一个顶点的简单链表]。

3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有[i(i+1)/2+j-1]个数据元素。 4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为[FILO]表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为[FIFO]表。

5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为[ABDECF]，中序遍历序列为[DBEAFC]，后序遍历序列为[DEBFCA]。

6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为[8]，有[64]个叶子结点。

7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的[出度]，第i列中所有非零元素个数之和等于顶点i的[入度]。

8. 设一组初始记录关键字序列(k1，k2，??，kn)是堆，则对i=1，2，?，n/2而言满足的条件为[ki<=k2i && ki<=k2i+1]。

9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(int r[n]) {

for(i=1;i<=n-1; i++) {

for(exchange=0,j=0; j<【n-i】;j++) if (r[j]>r[j+1]) {

temp=r[j+1];

【r[j+1]=r[j]】; r[j]=temp; exchange=1; }

if (exchange==0) return； } }

10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

struct record {

int key;

int others; };

int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1;

while(low<=high) {

【mid=(low+high)/2】; if(r[mid].key==k) return(mid+1);

else if(【r[mid].key>k】)

high=mid-1; else

low=mid+1; }

return(0); }

11. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有

【e】个和【2e】个。

12. AOV网是一种【有向无回路】的图。

13. 在一个具有n个顶点的无向完全图中，包含有【n(n-1)/2】条边，在一个具有n个顶点的有向完全图中，包含有【n(n-1)】条边。

14. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为【（12，40）】、【（ ）】、【（74）】和【（23,55，63）】。 15. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度【增加1】。 16. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为【O(log2n)】，整个堆排序过程的时间复杂度为【O(nlog2n)】。 17. 在快速排序、堆排序、归并排序中，【归并】排序是稳定的。 1. top1+1=top2

2. 可以随机访问到任一个顶点的简单链表 3. i(i+1)/2+j-1 4. FILO，FIFO

5. ABDECF，DBEAFC，DEBFCA 6. 8，64

7. 出度，入度

8. ki<=k2i && ki<=k2i+1 9. n-i，r[j+1]=r[j]

10. mid=(low+high)/2，r[mid].key>k 11. e 2e

12. 有向无回路

13. n(n-1)/2 n(n-1)

14. （12，40） （ ） （74） （23,55，63） 15. 增加1

16. O(log2n) O(nlog2n) 17. 归并

1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为【O(n)】。

2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为【s->next=p->next; p->next=s】（设结点的指针域为next）。 3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列【(1，3，2，4，5)】。 4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是【n-1】。 5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有129个结点数。 6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为【F==R】。 7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是【p->lchild==0&&p->rchild==0】。 8．简单选择排序和直接插入排序算法的平均时间复杂度为【O(n2)】。 9．快速排序算法的空间复杂度平均情况下为【O(nlog2n)】，最坏的情况下为【O(n)】。 10.散列表中解决冲突的两种方法是【开放定址法】和【链地址法】。

1. O(n)