《2010年暨南大学考研真题-830数据结构.doc》由会员分享，可在线阅读，更多相关《2010年暨南大学考研真题-830数据结构.doc（5页珍藏版）》请在三一文库上搜索。
1、2010年招收攻读硕士学位研究生入学考试试题（副题）*学科、专业名称：计算机技术、软件工程研究方向：各专业考试科目名称：830数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一.选择题(每题2分，共40分)1.具有n个顶点的完全有向图的边数为( ). A n(n-1)/2 B n(n-1) C n2 D n2-12.队列操作的原则是（ ） A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除3. 顺序栈S的Pop(S, e)操作弹出元素e，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top-) C. e=*(-s.top) D
2、. e=-s.top4. 对具有n个结点的有序表折半查找时，其时间复杂度是 ( ) 。 A. O(log2n） B. O(nlog2n） C. O(n） D. O(n2）5. 若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表6. 线性表的链接实现有利于( )运算 A.插入 B. 读表元素 C .查找 D.定位7. 设连通图G的顶点数为n,则G的生成树的边数为( ) A. n B. n-1 C.2n D. 2n-18.从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动（ ）个元素。 A.n-i B.n
3、-i+1 C.n-i-1 D. i9. 若有一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n,则第i个输出元素是（ ） A.n-i B.n-i-1 C.n-i+1 D.不确定10. 二叉树第i(i1)层上至多有( )个结点。 A. 2i B.2i C.2i-1 D.2i-1 11.串是一种特殊的线性表, 其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个12. 稀疏矩阵一般的压缩存储方法有两种,即: ( ) A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表考试科目： 数据结构 共 4 页，第 1
4、页13. 在AOE网中，完成工程的最短时间是（ ）。A从源点到汇点的最长路径的长度 B从源点到汇点的最短路径的长度C最长的回路的长度 D最短的回路的长度14. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。 A. 存储结构 B. 逻辑结构 C. 链式存储结构 D. 顺序存储结构15. 在线索化二叉树中，T所指结点没有左子树的充要条件是（ ）。A. T-left=NULL B. T-ltag=1 C. t-ltag=1且t-left=Null D. 以上都不对16.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。 As Bs-1 C
5、s+1 D2s17. 快速排序在( )情况下最不利于发挥其长处。. A. 被排序的数据量太大. B. 被排序数据中含有多个相同的关键字 C. 被排序的数据完全无序 D. 被排序的数据已基本有序18. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。A求关键路径的方法 B求最短路径的Dijkstra方法C广度优先遍历算法 D深度优先遍历算法19.通过一趟排序就能从整个记录序列中选择出具有最大（或最小）关键字的记录，这种排序方法是( ) 。 A. 堆排序 B. 快速排序 C. 直接插入排序 D.归并排序20. 设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要
6、修改指针的操作为( ) 。 A. p-next=p-next-next B. p=p-next C. p=p-next-next D. p-next=p二填空题(每空2分，共30分)1. 在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是 。2. 在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是： 和 。3.堆栈是一种操作受限的线性表，它只能在线性表的 进行插入和删除操作，对栈的访问是按照 的原则进行的。4.顺序查找方法适合于 存储结构；在等概率查找的条件下，对于表长是n的顺序表，其平均查找长度是 。5. 循环链表的主要优点是 。6. 一个算法的效率可为 效率和
7、 效率。7.对于一个具有n个记录的序列，若采用冒泡排序，记录之间最少的比较次数是 ，最多的比较次数是 。8.由n个权值构成的哈夫曼树共有 个结点。9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 。三判断题（每题1分，共15分,正确的选t，错误的选f） 考试科目： 数据结构 共 4 页，第 2 页1. 快速排序是排序算法中最快的一种。（ ）2. 二叉排序树的左、右子树都是二叉排序树。（ ）3. 对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ ）4. 用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结
8、点的个数有关，而与图的边数无关。（ ）5. 线性表中的每一个元素都有一个前驱和后继元素。（ ）6.若网中有几条关键路径，提高一条关键路径上的活动的速度，不能导致整个工程缩短工期。 （ ）7. 已知一颗树的先序序列和后序序列，一定能构造出该树。（ ）8. 双循环链表中，任一结点的前驱指针均为不空。（ ）9. 向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。 （ ）10. 对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是O(n2). ( )11. 算法和程序没有区别，在数据结构中二者是通用的。（ ）12. 若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是
9、该子树的先序遍历中的最后一个结点。( )13. 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（ ）14. 在n个顶点的无向图中，若边数n-1，则该图必是连通图。（ ）15. 一颗满二叉树同时又是一颗平衡树。（ ）四.应用题（35分）1.简述数据的逻辑结构和物理结构的区别和联系。（4分） 2.已知一个图如图1所示，给出2种不同的拓扑序列。（4分） 图1 3.已知一棵二叉树的中序遍历序列为DBEAFGC,前序遍历序列为ABDECFG，试问能不能唯一确定一棵二叉树,若能请画出该二叉树。（5分） 考试科目： 数据结构 共 4 页，第 3 页4.试问执行以下串函数会产
10、生怎样的输出结果？(6分)void compute( ) StrAssign(s, This is a book); Replace(s, SubString(s,3,7), ese are); StrAssign(t, Concat(s, s); StrAssign(u, mnmnmnmnmnmn); StrAssign(v, SubString(u,6,3); StrAssign(w, c); printf(t=, t, v=, v, u=, Replace(u, v, w);5.假设用于通信的电文仅由6个字母组成，字母在电文中出现的频率分别为：37，18，22，3，20，10，画出一棵哈
11、夫曼树，试为这6个字母设计哈夫曼编码。(8分)6. 输入一个正整数序列42,38,16,50,100,5,45,3,82,96,35，建立一棵二叉排序树，然后删除结点50。分别画出该二叉排序树及删除结点50后的二叉排序树。(8分)五算法设计题(30分)1算法填空（每空2分,共10分）下面算法在顺序表L中删除第i个元素，并保留在e中。Status ListDelete_Sq(SqList &L,int i, ElemType &e) if (iL.length_Sq(L) return ERROR; p= ; e=*p; q=L.elem+ ; for (+p;p=q; ) *(p-1)= ; L.length= ; return OK;2设计算法: 输入n个元素的值，创建带头结点的单链线性表L。 (8分)3假设在n个城市之间的公路网中，已知直达城市之间的乘车费用，各城市之间均存在通路，从V0城市开始乘车，经过若干个城市到S城市，有多条路线可以选择，设计算法：选择一条最节省费用的路线。 要求：（1）选择一种合适的数据结构，描述n个城市之间的公路网；（4分） （2）用伪代码描述求从V0城市到S城市最节省费用的路线。（8分） 考试科目： 数据结构 共 4 页，第 4 页