《数据结构》期末考试试题及答案

1、数据结构期末考试试题及答案(2003-2004 学年第 2 学期)单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（。、正确性(B). 可行性(C). 健壮性(D).输入性设S为C语言的语,计算机执行下面算法时算法的时间复杂度（ d。for(i=n-1；i=0；i-) for(j=0；jnext;p-next=Q.front-next;、p=Q.front-next;Q.front-next=p-next;、p=Q.rear-next; p-next= Q.rear-next;、p

2、=Q-next; Q-next=p-next;Huffman树的带权路径长度WPL等于（c）（A、除根结点之外的所有结点权值之和（B、所有结点权值之和（C、各叶子结点的带权路径长度之和（D、根结点的值线索二叉链表是利用（ c）域存储后继结点的地址。A、lchild（、data（C、rchild（Droot二、填空题逻辑结构决定了算法的设计，而存储结构决定了算法的现。栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈进行。线性表,a,a）的顺序存储结构中，设每个单元的长度为L，元素a12ni的存储地址LOC(a )为i已知一双向链表如下(指针域名为nextprior)：xxyqpe现 将 p

3、所 指 的 结 点 插 入 到 x 和 y 结 点 之 间 ， 其 操 作 步 骤为：；5n 个结点无向完全图的的边数为n个结点的生成树的边数为已知一有向无环图如下：BBFADGCE任意写出二种拓扑排序序列：、。 已知二叉树的中序遍历序列为后序遍历序列为 则该二叉树的先遍历序列为，层序遍历序列为。三、应用题1 设散列函数H(k)=k % 13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(6 分)构造HASH分别求查找成功和不成功时的平均查找长度。2 给定表（19,14,22,15,20,21,56,10）.（8 分）按元素在表中的次序，建立一棵二叉

4、排序树对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。画出对(2)中的遍历序列进行折半查找过程的判定树。已知二个稀疏矩阵ABABijVijV13-525224633725241342-152-9529558写出 A-B 压缩存储的三元组表。（5 分）已知一维数组中的数据为, 试写出插入排序（升序）程。并指出具有nA(8过程)ABCDEFA A 651B 653C 5 D 15776243636246F 求从顶点AA0.15B0.15C0.1D0.1EA0.15B0.15C0.1D0.1E0.2F0.3把这些字母和频率作为叶子结点及权值，完成如下工作(7 分，要有过程)。画出对应的Huf

5、fman计算带权路径长度WPL。A、C、EFHuffman7 已知有如下的有向网：AA25B3E646D12求顶点A（采用Dijkstra（6）三、 设计题（30分，每题10分,用C语言写出算法，做在答题上）已知线性表,a,a）以顺序存储结构为存储结构，其类型定义如下：12n#defineLIST_INIT_SIZE100顺序表初始分配容typedefstructElemtype*elem;/顺序存储空间基址intlength;当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为x 的结点（假若x 是唯一的。并求出其算法的平均时间复杂度。其算法函数头部如下： Status Lis

6、tDelete(Sqlist &L,Elemtype x)topana a12topana a12Elemtype*base;栈底指Elemtype*top;栈顶指Stack;设计算法，将栈顶元素出栈并存入e 中base设二叉链树的类型定义如下：typedefinttypedefstructnodeElemtypedata;structnode*lchild, *rchild;BinNode, *BinTree;/n is the number of leaves答案：选择题（每题 1 分）1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、填空题设计、实现特殊

7、、栈顶3LOC（a1）+(i-1)*L4p-next=q-next;q-next-prior=p; q-next=p;p-prior=q;5n(n-1)/2、n-1ADCBFEGABCDEFFGABC、ABC二、应用题1 （1）Hash 表（4 分）地址0123456789101112关键安132164572282412探测次数1712313112）查找成功的平均查找长度（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找长度1 分）（2+1+9+8+7+6+5+4+3+2+1）/13=2（、构造3 分）191914221015205621(2)、10 14 15 19

8、 20 21 22 56（2 分）（3分）3、(5 0.5)ijv13-524633741342-152185584、 初始关键字：1812255318第一趟：1218255318第第一趟：1218255318第二趟：1218255318第三趟：1218255318第四趟：1218182553O（n（1 分 5、7 分（1）4 分AB1C325D 4EF（2）4 分6、(1) 3 分EEFABCD（2）WPL=0.1*3+0.1*3+0.2*25*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10 （3 分）12A-AB）1 分 A-A、） 2

9、分 A-、）1分 A-A） 2 三，设计题（20 分）1、(10 分)StatusListDelete(Sqlist &L,ElemType x)int i,j;for(i=0;ilength;i+) if(L-elemi=x) if(i=L-length) return for(j=i;jlengthi-1;j+)L-elemj=L-elemj+1; L-length-;（8 分）2 分）设元素个数记为n，则平均时间复杂度为：E 2（10 分）1 nni1(n i) n 2void pop(Stack &S,Elemtype &e)if(S.top=S.base) return ERROR;

10、 S.top-;e=*s.top;2 （10 分 ） voidCountLeaves(BinTree T,int if(T)if(!(T-lchild)&!( T-rchild) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchild,n);1D 数据结构样卷及答案第一部分 选择题(30 分)一、 单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1算法指的是（ D）计算机程序 B解决问题的计算方法C排序算法 D解决问题的有限运算序列2线性表

11、采用链式存储时，结点的存储地址A必须是不连续的连续与否均可 C必须是连续的 D3将长度为n 的单链表链接在长度为m AO（1） BO（n） CO（m） DO（m+n） 4由两个栈共享一个向量空间B ） A减少存取时间，降低下溢发生的机率B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D设数组datam作为循环队列SQ 行出队操作后其头指针front值为（D ）Afront=front+1 Bfront=(front+1)%(m-1)Cfront=(front-1)%m Dfront=(front+1)%m ， ， 10 11如 下 陈 述 中 正 确 的 是 ） A串是一种

12、特殊的线性表 BCD空串就是空白串若目标串的长度为 nn/3时间复杂度是 ）AO（ ） BO（n） CO（n2） DO（n3） 8一个非空广义表的表头（ D） AB只能是子表C只能是原子 D可以是子表或原子9假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5对应的稀疏矩阵是（ ）103 3 2,2 1,0 数为( )A4 B5 C6 D7Ae B2e Cn2e Dn22e12 13 14 1512假设一个有n 个顶点和e ,vi ( )AO(n) BO(e) CO(n+e) DO(n*e) 13用某种排序方法对关键字序列进行排序时， 序列的变化情况如下：20，15，21，25，

13、47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）A选择排序 B希尔排序 C归并排序 D快速排序14适于对动态查找表进行高效率查找的组织结构是（ A有序表 B分块有序表 C三叉排序树 D线性链表15不定长文件是指（ ）A文件的长度不固定 B记录的长度不固定C字段的长度不固定 D关键字项的长度不固定第二部分 非选择题（共 70 分）二、填空题（本大题共10 小题，每小题2 分，若有两个空格，每个空格1 分，共20 分）写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。 16存储

14、（或存储结构） 17.pnextnext 18进栈和退栈 1912 20a4,8 21384 22abefcdg快速排序、堆排序、希尔排序25.多关键字数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。指向尾结点的直接前驱，则指向头结点的指针headp 表示为head= 。在串S=structuret 9 阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B B1 个元素a1,1,B?768 24在有序表（12，24，36，48，60，72，84）中二分查找关键字 72 时所需进行的关键字比较次数为 。25多重表文件和倒排文件都归属于 文件。三、解答题（4 5 20 分2

15、6画出下列广义表的共享结构图形表示请画出与下列二叉树对应的森林。a, b, c, d, e , ab c d e(1)画出该图的图形；（2）根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。已知一个散列表如下图所示：35 20 33 48 590 1 2 3 4 5 6 7 8 9 10 11 12其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：hi=(h(key)+ *h1(key)%m =0,1,.，m1其中h1(key)=key%11+1 回答下列问题：35，20，33 48 进行查找时，所需进行的比较次数各为多少？四、算法

16、阅读题（4 5 20 分） 30下列算法的功能是比较两个链串的大小，其返回值为：S1=S1nexts2=s2nexts2(s2!=NULL s2&!s1)s1(s1!=NULL s1&!s2)return 0comstr(s1,s2)=请在空白处填入适当的内容。int comstr(LinkString s1,LinkString s2)/s1 和 s2 为两个链串的头指针while(s1&s2) if(s1datedate)return1； if(s1dates2date)return1； ； ；if( )return1； if( )return1；阅读下面的算法LinkList mynot

17、e(LinkList/L if(L&L-next) q=L；L=Lnext；p=L；S1： while(pnext)p=pnext；S2： pnext=q；qnext=NULL；return L；请回答下列问题：说明语句S1的功能；说明语句组S2的功能；设链表表示的线性表为表。查询链表的尾结点将第一个结点链接到链表的尾部，作为新的尾结点返回的线性表为（a2,a3,.,an,a1）假设两个队列共享一个循环向量空间（参见右下图其类型Queue2定义如下：typedef structDateType dataMaxSize； int front ,rear ；Queue2；i=0 reari分别为第

18、i i 个队列的入队操作。int EnQueue (Queue2*Q,int i,DateType x)/若第 i 个队列不满，则元素x 入队列，并返回 1；否则返回 0 if(i1)return 0；if(Qreari=Qfront return0； Qdata =x；Qreari= ; return1；(i1)%2(或 1i)(Qreari)%Maxsize 33typedef struct node DateType Struct node * ListNode；typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inor

19、der (BinTree T)LinkList s； If(T)Inorder(Tlchild)；If (!Tlchild)&(!Trchild) sdata=Tdata； snext=Leafhead；Leafhead=s；Inorder(Trchild)；对于如下所示的二叉树画出执行上述算法后所建立的结构；说明该算法的功能。 中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead 为头指针的逆序单链（或按二叉树中叶子结点数据自右至左链接成一个链表五、算法设计题（10 分）34阅读下列函数arrange()int arrange(int a&#;,int 1,int h,int x)/1 和 h 分别为数据区的下界和上界int i,j,t； i=1；j=h； while(ij)while(i