数据结构期末考试试题.doc

《数据结构期末考试试题.doc》由会员分享，可在线阅读，更多相关《数据结构期末考试试题.doc（70页珍藏版）》请在三一办公上搜索。

1、“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A HLps p一nextHL B p一nextHL；HLp3 C p一nextHl；pHL； D p一nextHL一next;HL一nextp； 2n个顶点的强连通图中至少含有( )。 A.nl条有向边 B.n条有向边 C.n(n1)2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)C.O(1Ogzn) D.O(n2)4由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它

2、的带权路径长度为( )。 A24 B48C 72 D 535当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型6向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 AO(n) BO(1) CO(n2) DO(10g2n)二、填空题(每空1分，共28分)1数据的存储结构被分为、和四种。 2在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。3中缀表达式 3十x*(2.456)所对应的后缀表达式为。 4在一棵高度为h的3叉树中，最

3、多含有结点。5假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为 6在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。 7当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到位置为止。 8表示图的三种存储结构为、和。 9对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。 10从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和 11假定对长度n144的线性表进行索引顺序查找，并

4、假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为 12一棵B树中的所有叶子结点均处在上。 13每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。 14快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。 三、运算题(每小题6分，共24分) 1假定一棵二叉树广义表表示为a(b(c，d)，c(，8)，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2已知一个带权图的顶点集V和边集G分别为： V0，1，2，3，4，5；

5、E=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10， 则求出该图的最小生成树的权。 最小生成树的权； 3假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为。 4有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数：。四、阅读算法，回答问题(每小题8分，共16分) 1VOldAC(List&L) InitList(L)； InsertRear(L;2

6、5)； InsertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i5; i+) if (ai20)InsertFront(L，ai)； elselnsertRear(L，ai)； 该算法被调用执行后，得到的线性表L为： 2void AG(Queue&Q) InitQueue(Q)； inta56，12，5，15，8； for(int i0;i5; i+)QInsert(Q，ai)； QInsert(Q，QDelete(Q)； QInsert(Q，20)； QInsert(Q，QDelete(Q)十16)； while(!QueueEmpty(Q)co

7、utQDelete(Q)”； 该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1从一维数组An)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。 IntBinsch(ElemTypeA，Intlow，int high，KeyTypeK) if(lowhigh) int mid(low+high)2； if(KAmid.key)； else if (KdataX)return 1; 根结点的层号为1 向子树中查找x结点 else int clNodeLevel(BT一left，X)； if(cl1)retu

8、rn cl+1; int c2 ； if； 若树中不存在X结点则返回o else return 0； 六、编写算法(8分) 按所给函数声明编写一个算法，从表头指针为HL的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。 EIemType MaxValue(LNOde*HL);“数据结构”期末考试试题答案 一、单选题(每小题2分，共12分) 评分标准；选对者得2分，否则不得分。 1B 2B 3C 4D 5B 6A 二、填空题(每空1分，共28分) 1顺序结构 链接结构 索引结构 散列结构(次序无先后) 2值(或data) 子表指针(或sublist) 33 x 24

9、56一*十 4(3h一1)2 5 5 18 6小于 大于(或大于等于) 7向上 堆顶 8邻接矩阵 邻接表 边集数组(次序无先后) 9O(n2) O(e) 10 1 3 1113 O() 12同一层 13插人 选择 14O(nlog2n) O(n2) 三、运算题(每小题6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成树的权：31 6分 3(84，79，56，42，40，46，50，38) 6分 4带权路径长度：131 3分 高度：5 2分 双分支结点数：6 1分四、阅读算法，回答问题(每小题8分

10、，共16分) 评分标准：每小题正确得8分，出现一处错误扣4分，两处及以上错误不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1feturn mid 2分 returnBinsch(A，low，mid一1，K) 2分 returnBmsch(A，mid+1，high，K) 2分 2NodeLevel(BT一right，X) 3分 (c2=1)returnc2十1 3分六、编写算法(8分) 评分标准：请参考语句后的注释，或根据情况酌情给分。 ElemType MaxValue(LNodeO*

11、HL。) if (HL=NUlL) 2分 cerrLinked llst is empty!”data； 3分 LNOde*p=HI一next； 4分 while(P!：NULL) 7分 if(maxdata)maxp一data； pp一next； returnmax； 8分 一、 单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。1. 算法必须具备输入、输出和 C A. 计算方法B. 排序方法C解决问题的有限运算步骤D. 程序设计方法2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是 A

12、 A. 访问第i个节点（1in）B. 在第i个节点后插入一个新节点（1in）C. 删除第i个节点（1in）D. 将n个节点从小到大排序3单链表的存储密度 C A大于1B. 等于1C小于1D. 不能确定4设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 B A23415B. 54132C23145 D. 154325. 循环队列SQ的存储空间是数组dm，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是 D Afront=front+1 B. front=(front+1)%(m-1)C. front=(front

13、-1)%m D. front=(front+1)%m6. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B A. O(1) B. O(n) C. O(n2) D. O(nlogn)7. 设二维数组A0.m-10.n-1按行优先顺序存储，则元素Aij的地址为 B A LOC(A00)+(i*m+j) BLOC(A00)+(i*n+j)C. LOC(A00)+(i-1)*n+j-1 D. LOC(A00)+(i-1)*m+j-1 8. 一个非空广义表的表头 D A一定是子表B. 一定是原子C不能是子表D. 可以是原子，也可以是子表9具有n个节点的完全二叉树的深度为 A

14、 Alog2(n+1) -1 B. log2n+1 C. log2n D. log2n10. 若要惟一地确定一棵二叉树，只需知道该二叉树的 D A前序序列B. 中序序列C前序和后序序列D. 中序和后序序列11在一个无向图中，所有顶点的度数之和等于图的边数的倍 C A1/2 B. 1C. 2 D. 412. 拓扑排序运算只能用于 C A带权有向图B. 连通无向图C有向无环图D. 无向图13在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D A希尔排序B. 冒泡排序C插入排序D. 选择排序14下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是 C A堆排序B. 冒泡排

15、序C直接选择排序D. 快速排序15二分查找要求节点 A A有序、顺序存储B. 有序、链接存储C无序、顺序存储D. 无序、链接存储二、 填空题（本大题共10小题，每小题2分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16数据的逻辑结构分为两大类，它们是线性结构和非线性结构 。17在单链表中（假设结点指针域名称为next），删除指针P所指结点的后继结点的语句是 p-next=p-next-next 。18已知循环队列用数组datan存储元素值，用front,rear分别作为头尾指针，则当前元素个数为 (rear-front+n)%n 。19 若n为主串长，m 为子串

16、长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为_（n-m+1）m_ _。20 广义表(a),(b),j,(d)的表尾是_(b),j,(d)_ _。21 已知二叉树有61个叶子节点，且仅有一个孩子的节点数为45，则总节点数为_166 _。22 解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个队列 结构。23 n 个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_O(n+e)_。24 对于n个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为_O（n2）_。25在一个长度为n的顺序表中的第i个元素（1in）之前插入一个元素时，需向后移n-i+1 个元

17、素。三、 解答题（本大题共4小题，共25分）26. 对于下面的稀疏矩阵，画出其三元组法存储表示(假设下标从0开始)。（5分）0 0 14 0 0 00 0 0 0 -6 07 0 0 0 0 240 0 0 18 0 00 15 0 0 0 0答案:021414-6207252433184115行号 列号 值012345 27. 已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。（5分）中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA答案:ABCDEFHGJKIL28设有一个关键码的输入序列55,31,11,37,46,73,63,02,07，（7分）（1） 从空

18、树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(3分)（2） 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。(4分)29已知一个图的邻接表如下所示。（8分）（1） 画出该图的图形；(4分)（2） 根据邻接表分别画出从顶点a出发进行深度优先和广度优先遍历所生成的生成树。(4分)abcdef12555243答案：四、 算法阅读题（本大题共3小题，每小题5分，共15分）30设线性表的n个结点定义为（a0,a1,an-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最

19、大可容纳项数为MaxSize)Template int SeqList:Insert(Type &x, int i) If (ilast+1 | last= (1) ) return 0; Else Last+; For(int j=last;ji;j-) dataj= (2) ; (3) ; Return 1; Template int seqList:Remove(Type &x) int i=Find(x); if(i=0) last-; for (int j= (4) ;jtop!=StackSize-1)s-data+s-top=x;DataType Pop(SeqStack *s)

20、if(s-top!=-1) return s-datas-top-;void main( ) DataType i; SeqStack s; s.top=-1; scanf(“%d”,&i); while(i!=-1) push(&s,i); scanf(“%d”,&i); while(s-top!=-1) i=Pop(&s); printf(“%6d”,i);答案:(1)程序的功能是把输入的一串整数(用-1做结束标记) ，按照与输入相反的次序输出。用栈实现这一功能。（2）输出结果 8 7 6 5 4 3 2 1。 32. 已知二叉树的存储结构为二叉链表，阅读下面算法。说明该算法的功能。Tem

21、plateint BinaryTree:height(BinTreeNode *t) if(t=NULL) return 1; int h1=height(t-leftChild); int hr=height(t-rightChild);return 1+(h1hr?h1:hr); 答案：该算法的功能是统计二叉树的高度。五、 算法设计题（本题共10分）33设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法。（1）统计二叉树中度为1的结点个数；（5分）（2）统计二叉树中度为2的结点个数。（5分） （提示：递归算法如32题所示）解答：（1）统计二叉树中度为1的结点个数。Temp

22、lateInt BinaryTree :Degree1(BinTreeNode *t)constIf(t=NULL) return 0;If(t-leftchild!=NULL &t-rightchild=NULL | t-leftchild=NULL &t-rightchild!=NULL) Return 1+Degree1(t-leftchild)+Degree1(t-rightchild);Return Degree1(t-leftchild)+Degree1(t-rightchild);(2) 统计二叉树中度为2的结点个数。TemplateInt BinaryTree :Degree2

23、(BinTreeNode *t)constIf(t=NULL) return 0;If(t-leftchild!=NULL &t-rightchild!=NULL ) Return 1+Degree2(t-leftchild)+Degree2(t-rightchild);Return Degree2(t-leftchild)+Degree2(t-rightchild);“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A HLps p一nextHL B p一nextHL；HLp3 C p一nextHl；pHL

24、； D p一nextHL一next;HL一nextp； 2n个顶点的强连通图中至少含有( )。 A.nl条有向边 B.n条有向边 C.n(n1)2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)C.O(1Ogzn) D.O(n2)4由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A24 B48C 72 D 535当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.

25、常值引用型6向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 AO(n) BO(1) CO(n2) DO(10g2n)二、填空题(每空1分，共28分)1数据的存储结构被分为、和四种。 2在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。3中缀表达式 3十x*(2.456)所对应的后缀表达式为。 4在一棵高度为h的3叉树中，最多含有结点。5假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为 6在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。 7当向一个小根堆插入一个具有最小值的元素时，

26、该元素需要逐层调整，直到被调整到位置为止。 8表示图的三种存储结构为、和。 9对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。 10从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和 11假定对长度n144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为 12一棵B树中的所有叶子结点均处在上。 13每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最

27、小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。 14快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。 三、运算题(每小题6分，共24分) 1假定一棵二叉树广义表表示为a(b(c，d)，c(，8)，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2已知一个带权图的顶点集V和边集G分别为： V0，1，2，3，4，5； E=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10， 则求出该图的最小生成树的权。 最小生成树的权； 3假定一组记录的排序码为(46，79，56，38，40，

28、84，50，42)，则利用堆排序方法建立的初始堆为。 4有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数：。四、阅读算法，回答问题(每小题8分，共16分) 1VOldAC(List&L) InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i5; i+) if (ai20)InsertFront(L，ai)； elselnsertRear(L，ai)； 该算

29、法被调用执行后，得到的线性表L为： 2void AG(Queue&Q) InitQueue(Q)； inta56，12，5，15，8； for(int i0;i5; i+)QInsert(Q，ai)； QInsert(Q，QDelete(Q)； QInsert(Q，20)； QInsert(Q，QDelete(Q)十16)； while(!QueueEmpty(Q)coutQDelete(Q)”； 该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分) 1从一维数组An)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回

30、一1。 IntBinsch(ElemTypeA，Intlow，int high，KeyTypeK) if(lowhigh) int mid(low+high)2； if(KAmid.key)； else if (KdataX)return 1; 根结点的层号为1 向子树中查找x结点 else int clNodeLevel(BT一left，X)； if(cl1)return cl+1; int c2 ； if； 若树中不存在X结点则返回o else return 0； 六、编写算法(8分) 按所给函数声明编写一个算法，从表头指针为HL的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链

31、表为空则中止运行。 EIemType MaxValue(LNOde*HL);“数据结构”期末考试试题答案 一、单选题(每小题2分，共12分) 评分标准；选对者得2分，否则不得分。 1B 2B 3C 4D 5B 6A 二、填空题(每空1分，共28分) 1顺序结构 链接结构 索引结构 散列结构(次序无先后) 2值(或data) 子表指针(或sublist) 33 x 24 56一*十 4(3h一1)2 5 5 18 6小于 大于(或大于等于) 7向上 堆顶 8邻接矩阵 邻接表 边集数组(次序无先后) 9O(n2) O(e) 10 1 3 1113 O() 12同一层 13插人 选择 14O(nlog2n) O(n2) 三、运算题(每小题6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成树的权：31 6分 3(84，79，56，42，40，46，50，38) 6分 4带权路径长度：131 3分 高度：5 2分 双分支结点数：6 1分四、阅读算法，回答问题(每小题8分，共16分) 评分标准：每小题正确得8分，出现一处错误扣4分，两