2013秋学期数据结构-期未复习(成人2012)-参考答案

2013年秋学期数据结构期未考试-复习题（2012级）-参考答案

一．判断题。

1. 具有相同逻辑结构的数据可以采用不同的存储结构。 (? ) 2. 算法分析的前提是算法的时空效率高。 ( ) 3. 程序设计框图就是一种图形化的算法。 (? ) 4. 线性表的顺序存储结构要比链式存储结构节省存储空间。 ( ) 5. 任何一个链表都可以根据需要设置一个头结点。 (? ) 6. 在长度为n的顺序表的第i个位置插入一个数据元素,i的合法值为1<=i<=n. ( ) 7. 双向链表的头结点指针要比线性链表的头结点指针占用更多的存储空间。 ( ） 8. n个元素进队列的顺序一定与它们出队列的顺序相同。 (? ) 9. n个元素进栈的顺序与它们出栈的顺序一定是相反的。。 ( ） 10. 采用循环链表作为存储结构的队列称为循环队列。 ( ) 11. 在树型结构中，每一个结点都有而且只有一个前驱结点。 ( ) 12. 在度为k的树中，每个结点最多有k-1个兄弟结点。 ( ? ） 13. 二叉树就是度为2的有序树是二叉树。 ( ) 14. 在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。 (? ) 15. 由二叉树的任何两种遍历序列都可以唯一确定一棵二叉树。 ( ) 16. 在哈夫曼树中，权值相同的叶结点都在同一层上。 ( ) 17. 分块索引查找的效率与文件中的记录被分成多少块有关。 (? ) 18. 在利用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存放在一片地址连续

的存储单元中。 ( ) 19. 在序列中各元素已经基本有序的情况下，采用快速排序方法的时间效率最高。 ( ) 20. 在各类方法中，简单排序的辅助空间都是1，而先进排序方法辅助空间都比较大。 ( )

二．填空

1. 一般情况下,算法独立于具体的_计算机_，与具体的程序设计语言_无关。

2. 数据结构中的算法，通常采用最坏时间复杂度和____________两种方法衡量其效率。（平均时间

复杂度）

3. 算法分析的前提是算法的__________。（正确性）

4. 在一个长度为n的顺序表中插入第i个元素时，需移动________个元素。（n-i+1） 5. 为了实现随机访问,线性结构应该采用___顺序____________存储结构。

6. 如果需要频繁地对线性表进行插入和删除操作,则该线性表宜采用__________存储结构。（链式）

7. 在非空双向循环链表中由 q 所指的链结点前面插入一个s所指的链结点的动作依次

为:s->prior=q->prior; p->next=q;q->prior=s;__________________。(空白处为一条赋值语句) (s->prior->next=s; )

8. 栈和队列的逻辑结构都是____________________。（操作受限的线性表） 9. 实现二叉树的按层次遍历算法时需要用到_______结构。（队列）

10. 实现二叉树的中序递归遍历算法的非递化时需要用到_______结构。（栈） 11. 已知一棵哈夫曼树含有n0个叶子结点，则该树中共有_________个非叶子结点。(n0-1) 12. 已知一棵哈夫曼树含有n0个叶子结点，则该树中共有_________个结点。(2n0-1)

13. 采用逐点插入法建立序列(34,17,9,26,56,43,79,51,15,31)的二叉排序树后，查找数据元素51共进行_______次元素间的比较。（4）

34

14. n个顶点的连通无向图，其边的条数至少为__________。（n-1） 175615. n个顶点的连通有向图，其有向边的条数至少为__________。（n） 16. 第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个9267943顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。（简单回路） 15315117. 对线性表采用折半查找方法，该线性表必须采用_________存储结

二-13题图构，并且_________。（顺序、元素按关键字排列有序）

18. 在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行_______次元素

间的比较。（3）

19. 若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查找长度

ASL=___(n+1)/2_________。

20. 索引文件包括__索引表__和___主表（基本文件）_______两个部分。

21. 具有144项的表分成_______块最好，若每块的最佳长度为8，则平均查找长度为___或_______。

（12、13/8（折半））

22. 散列函数建立了___________________之间的对应关系。_(记录的关键字与存储地址) 23. 一个好的散列函数是指_________________________________________。(使得到的哈希地址尽可

能均匀分布在事先已知的空间范围，并函数尽可能简单)

24. 处理冲突的方法通常有__________________、_______________、___________________。(开放

定址法__、_再哈希法__和__链地址法__)

25. 当参加排序的数据量较大,元素的分布又比较随机,并且只需要选出最大或最小的部分元素时，宜

选择______排序。（堆）

三．选择题(

1. 数据的不可分割的最小数据单位是______。 A

(A)数据项 (B)数据记录 (C)数据元素 (D)数据变量 2. 抽象数据类型（ADT）的三个组成部分分别为____。B

(A)数据元素、逻辑结构和存储结构 (B)数据对象、数据关系和基本操作 (C)数据项、数据元素和数据类型 (D)数据元素、数据结构和数据类型

3. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为

_______。D

(A)无头结点的双向链表 (B)带头指针的循环链表 (C)无头结点的单链表 (D)带尾指针的循环链表

4. 若长度为n的非空线性表采用顺序存储结构,删除表的第i个数据元素,i的合法值应该是

____________。C (A)i>0 (B)i<=n (C)1<=i<=n (D)1<=i

5. 若长度为n的线性表采用顺序存储结构,在表的第i个位置插入一个数据元素,需要移动表中

________个元素。D (A)i (B)n+i (C)n-i-1 (D)n-i+1 6. 链表所占用的存储空间一定是_________。D

(A)无序的 (B)连续的 (C)不连续的 (D)部分连续 7. 关于栈和队列的说法中正确的是______。A

(A)栈和队列都是线性结构 (B)栈是线性结构，队列不是线性结构 (C)栈不是线性结构，队列是线性结构 (D)栈和队列都不是线性结构

8. 假设以数组A[M]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下

一个存储位置，则队头元素所在的存储位置为________。A (A)(rear-length+M-1)％M (B) (rear-length)％M (C)(rear-length+M)％M (D) (rear-length+M+1)％M

9. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是___。C

(A) 2 3 4 1 5 (B) 3 2 1 5 4 (C) 3 4 5 1 2 (D) 1 2 3 4 5

10. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个

度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有__________个叶结点。D (A) 35 (B) 28 (C) 77 (D) 78

11. 已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为_____。C

(A)6 (B)7 (C)8 (D)9 12. 设某棵二叉树中有1000个结点，则该二叉树的最小高度是_____。D

(A)8 (B)9 (C)10 (D)11

13. 任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置______。A

(A)不会发生改变 (B)都会发生改变 (C)有可能会发生改变 (D)部分会发生改变 14. 分块索引是指在文件的索引表中_______。D

(A)为每个字段设一个索引项 (B)为每个记录设一个索引项 (C)为每组字段设一个索引项 (D)为每组记录设一个索引项 15. 按排序过程中依据的原则分类，快速排序属于_____。B

(A)插入类的排序方法 (B)交换类的排序方法 (C)选择类的排序方法 (D)归并类的排序方法 16. 在二叉排序树中进行查找的效率有关的是____。A

(A)二叉排序树的深度 (B)二叉排序树的结点的个数 (C)被查找结点的度 (D)二叉排序树的存储结构

17. 对n个记录的文件进行排序，下列排序方法中所需要的辅助存储空间最小的为___。B

(A)快速排序 (B)堆排序 (C)希尔排序 (D)归并排序

18. 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是_____。B

(A)冒泡排序 (B)希尔排序 (C)快速排序 (D)堆排序 19. 下列查找方法中，不属于动态的查找方法是_____。A

(A)散列法 (B)平衡树法 (C)二叉排序树法 (D)斐波那契查找法

20. 若有16个元素的有序表存放在一维数组A[17]中，第一个元素放A[1]中，现进行二分查找，则

查找A[11]的比较序列的下标依次为____。D (A) 9，13，11 (B) 9，12，11 (C) 9，13，10，11 (D) 8，12，10，11

四．简答题

1. 什么是数据？什么是结构？“数据结构”课程主要研究什么内容？

答：一切可以用计算机存储和表示的对象；包括数字、声音、图像等

结构：也叫关系，有集合，线性表，树和图

研究内容：数据的逻辑结构，物理结构及操作实现

2. 依次读入数据元素{a,b,c,d,e,f,g}，进栈时每进一个元素，下一个操作可以是进栈或出栈，如此进

行则至栈空时出栈的元素能构成的序列是以下的哪个序列，如能请写出操作过程，如不能则请说明原因。

{b,d,f,e,c,g,a}，{e,f,d,g,b,c,a } 答：前者可以。后者不可以。

3. 已知某二叉树的前序序列为ABDEGCFHI，中序序列为DBGEACHFI，请画出该二叉树，及中序线索树。。 答：

AABBDGCEFHICDEFGHI

4. 假设某通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：0.07，0.26，0.02，0.29，0.13，0.09，0.03，0.11，试（1）构造哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；(2)为这8个字符设计哈夫曼编码。

答：(1)

(2) a：0101；b：10；c：01000；d：11；e：011；f：000；g：01001；h：001

5. .折半查找过程可以利用一棵判定树来描述。请画出n=13时的判定树。

7[1,6]3[1,2]1[4,6]5[8,9]8[8,13]10[11,13]1224691113

6. 对关键字表{26，65，78，52，41，13，49，59}进行升序排序，分别采用起泡排序和快速排序、简单选择排序和堆排序算法，写出每一趟结束时的结果，并指出相应排序方向的稳定性。 答：起泡排序：

初始：{26，65，78，52，41，13，49，59} 一趟：{26，65，52，41，13，49，59} 78 二趟：{26，52，41，13，49，59} 65，78 三趟：{26，41，13，49，52} 59，65，78 四趟：{26，13，41，49} 52，59，65，78 五趟：{13，26，41} 49，52，59，65，78 六趟：13，26，41，49，52，59，65，78

快速排序：

初始：{26，65，78，52，41，13，49，59} 一趟：（13）26 ( 78，52，41，65，，49，59} 二趟：13，26（59，52，41，65，49 ) 78 三趟：13，26（49，52，41) 59 （65）78 四趟：13，26（41） 49（52），59，65，78 五趟：13，26，41，49，52，59，65，78

简单选择排序：

初始：{26，65，78，52，41，13，49，59} 一趟：13（65，78，52，41，26，49，59} 二趟：13，26（78，52，41，65，49，59} 三趟：13，26，41（52，78，65，49，59} 四趟：13，26，41，49（78，65，52，59} 五趟：13，26，41，49，52（65，78，59} 六趟：13，26，41，49，52，59（78，65} 七趟：13，26，41，49，52，59，65（78}

堆排序：

初始：{26，65，78，52，41，13，49，59} 初始堆：78，65，49，59，41，13，26，52

一趟 交换：52，65，49，59，41，13，26（78） 调整为堆：65，59，49，52，41，13，26（78） 二趟 交换：26，59，49，52，41，13，（65，78） 调整为堆：59，52，49，26，41，13，（65，78） 三趟 交换：13，52，49，26，41，（59，65，78） 调整为堆：52，41，49，26，13，（59，65，78） 四趟 交换：13，41，49，26，（52，59，65，78） 调整为堆：49，41，13，26，（52，59，65，78） 五趟 交换：26，41，13，（49，52，59，65，78） 调整为堆：41，26，13，（49，52，59，65，78） 六趟 交换：13，26，（41，49，52，59，65，78） 调整为堆：26，13，（41，49，52，59，65，78） 七趟 交换：13，（26，41，49，52，59，65，78）

五．算法题

typedef struct node { typedef struct node{ Elemtype data; int data; struct node *next; struct node *lchild,*rchild; }SLNode, *SLinkedList; }BTNode, *BiTree;

1. 阅读算法f un,并回答下列问题：

(1)设队列Q=(1，4，7，3，6，9)。写出执行算法fun后的队列Q; (2)简述算法fun的功能。

void fun(SqQueue &Q){ QElemType e; if (!QueueEmpty(Q)){ e=DeQueue(Q); fun(Q);

EnQueue(Q,e); } }

(1) Q=（9，6，3，7，4，1） (2) 将队列中的元素逆置

2. 下列算法利用折半查找方法在有序表L中插入元素x，并保持表L的有序性。请在空缺处填入合适的内容，使其成为一个完整的算法。 void BinInsert(SqList &L,ElemType x) { int low=1,high=L.length,mid,i; while(low<=high)

{ mid= (1) ; // (1)：（low+high）/2 if (x

else (2) ; //(2)：low=mid+1 }

for(i=L.length; (3) ;i--) //(3)：i>=low L.elem[i+1]=L.elem[i];

(4) ; //(4)：L.elem[low]=x; L.length++; }

3. 已知长度为n的线性表A采用顺序存储结构,并且每个数据元素均为一个无符号整数,请写一算法,删除线性表中的所有奇数。 void Delete_Odd(Sqlist &A) { i=0;

while(i

if(A.elem[i]%2 != 0 ) {

for(j=i+1;j

} //end of if else i++; }//end of while }//end

4. 已若二叉树采用二叉链表存储结构，请写出求该二叉树的高度的递归算法。

int High(BiTree T)//求二叉树中的深度 { if( !T ) return 0; //空树没有叶子 else {

lh=High(T->leftchild);//左子树高 rh=High(T->rightchild); //右子树高

return (lh>rh?lh+1:rh+1);//左右子树高度中较高者加1

}//High

5. 二叉树是指每个结点至多有2个子树，并且其子树有左右之分的一种树型结构。请编写算法计算二叉树T中度数分别为0、1和2的结点个数。

(1)只求叶子的：int leaf(BiTree T) (框架： 分) {{if( !T) return 0; //空树没有叶子 (指出空树情况： 分)

else if( !T->lchild && !T->rchild ) return 1; //如果是叶子结点 (指出叶子情况： 分) else return (leaf(T->lchild)+leaf(T->rchild) );//非叶子时为左右子树叶子之和(指出非终端结点情况： 分)

}// leaf

(2)三类结子同时求的，

void Count_node(BinaryTree r, int &no,int &n1,int &n2)

{ //调用之前，no,n1,n2均为0

if(r) // { if((r->lChild==NULL) &&(r->rChild!=NULL)) n0++;

if((r->lChild==NULL) &&(r->rChild!=NULL)) n1++; if((r->lChild!=NULL) &&(r->rChild==NULL)) n1++; if((r->lChild!=NULL) &&(r->rChild!=NULL)) n2++; count_node(r->lChild,n0,n1,n2); count_node(r->rChild,n0,n1,n2); }

}

本文来源：https://www.bwwdw.com/article/j2vp.html