2012年暨南大学数据结构考研真题

2012年全国硕士研究生统一入学考试自命题试题

********************************************************************************************

学科与专业名称：计算机技术，软件工程 考试科目代码与名称：830 数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一. 选择题(每题2分，共30分) 1．队列操作的原则是（ ）。 A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除 2. 一个栈的进栈序列是a, b, c, d, e, 则栈的不可能的输出序列是（ ）。 A. edcba B. decba C. dceab D. abcde 3. 采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为 （ ）。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 4. 线性表的链接实现有利于( )运算。 A. 读表元素 B.插入 C. 查找 D. 定位 5. 设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( )。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 6. 在内部排序中,排序时不稳定的有( )。 A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序 7. 在AOE网中，完成工程的最短时间是（ ）。 A．从源点到汇点的最长路径的长度 B．从源点到汇点的最短路径的长度 C．最长的回路的长度 D．最短的回路的长度 8．以下（ ） 方法所用辅助存储空间最大。 A． 堆排序 B． 希尔排序 C．快速排序 D．归并排序 9．具有8个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 10. 对具有n个结点的有序表中折半查找时，其时间复杂度是（ ）。 A．O(nlog2n） B．O(log2n） C．O(n） D．O(n2） 11．如果希望对平衡二叉树遍历的结果是升序的，应采用（ ）遍历方法。 A．先序 B．中序 C．后序 D．层次 考试科目： 数据结构 共 5页，第 1 页

12. 稀疏矩阵一般的压缩存储方法有两种,即:（ ）。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 13. 循环队列中是否可以插入下一个元素 （ ）。 A. 与曾经进行过多少次插入操作有关. B. 只与队尾指针的值有关,与队头指针的值无关. C. 只与数组大小有关,与队首指针和队尾指针的值无关 D. 与队头指针和队尾指针的值有关. 14. 在线索化二叉树中，T所指结点没有左子树的充要条件是（ ）。 A．T->left=NULL B．T->ltag=1 C．t->ltag=1且t->left=Null D．以上都不对 15. 以下说法中不正确的是（ ）。 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法 二．填空题(每题2分，共20分) 1．一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为 。 2．数据结构按逻辑结构可分为两大类，它们分别 。 3．由n个权值构成的哈夫曼树共有 个结点。 4．在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是： 和 。 5．单链表中设置头结点的作用是 。 6．一棵深度为k的满二叉树的结点总数为 ，一棵深度为k的完全二叉树的结点总数的最小值为 。 7．一个无向图有n个顶点和e条边，则所有顶点的度的和为 。 8．在二叉链表中判断某指针p所指结点为叶子结点的条件是 。 9．堆栈是一种操作受限的线性表，它只能在线性表的 进行插入和删除操作，对栈的访问是按照 的原则进行的。 10．若某记录序列的关键字序列是（235，346，021，558，256），用链式基数排序方法排序，第一次收集的结果是 。 考试科目： 数据结构 共5 页，第 2 页

三．判断题（每题1分，共10分，正确的选t，错误的选f） 1．如果T2是由树T1转换而来的二叉树,那T1中结点的先序就是T2中结点的先序。（ ） 2．在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（ ） 3．线性表中的每一个元素都有一个前驱和后继元素。（ ） 4．按中序遍历一颗二叉排序树所得到的中序遍历序列f是一个递增序列。（ ） 5．若网中有几条关键路径，提高一条关键路径上的活动的速度，不能导致整个工程缩短工期。 （ ） 6．一颗满二叉树同时又是一颗平衡树。（ ） 7．数据结构是研究数据的物理结构、逻辑结构以及它们之间的相互关系。（ ） 8. 拓扑排序是一种内部排序的算法。( ) 9.已知一颗树的先序序列和后序序列，一定能构造出该树。（ ） 10．n阶对称矩阵可压缩存储到n2/2个元的空间中。( ) 四. 简答题（50分） 1. 给定关键字序列 T=(65，57，45，39，12，98，86，35），采用快速排序算法，以第一个元素为枢轴，对该序列由小到大排序，并写出具体排序过程。 (8分) 2. 简述下列算法的功能。（6分） void Process(LinkList &L, int x, int y) { // L线性表的元素递增有序排列 LinkList p=L, q, s; if ((p->next) && (x<=y)) { while (p->next && p->next->data<=x) p=p->next; If (p->next) return ERROR; q=p->next; while (q->next && q->next->datanext; free(s); } p->next=q->next; free(q); } } 3. 使用克鲁斯卡尔算法构造出图1所示的图G的一棵最小生成树（要求写出构造过程）。（10分） 图1 考试科目： 数据结构 共 5 页，第3页

4. 已知一个图如图2所示，若从顶点a出发，按深度优先搜索法进行遍历，写出可能得到的一种顶点序列；按广度优先搜索法进行遍历，写出可能得到的一种顶点序列。 (4分) 图2 5. 给定图3所示带权有向图及其邻接矩阵，利用Floyd算法，求每一对顶点之间的最短路径及其路径长度（要求写出求解过程）。 （12分） 图3 6．给出一组关键字的序列为{ 12，15，34，37，39，22，38，66，74，80，107 }，假设哈希函数为Hash(key)=key mod 11，画出按照链地址法处理冲突构造所得的哈希表，并在记录的查找概率相等的前提下，计算成功查找的平均查找长度。（10分） 五．算法填空，（每空2分,共16分） 1. 下面的算法将元素e加入队列Q中，请在 处填上适当内容，使其成为一个完整算法。 typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue, * LinkQueuePtr; Boolean EnQueue (LinkQueuePtr Q, QElemType e) { //元素e加入到队列Q中 p = ; if (!p) return FALSE; 考试科目： 数据结构 共5 页，第4页

p->data = e; p->next = ; = p; Q->rear = ; return TRUE; } 2. 下面是先序遍历二叉树的算法非递归算法，请在 处填上适当内容，使其成为一个完整算法。 typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; void PreOrderTraverse(BiTree ,Status(*Visit)(TElemType)) { //采用二叉链表存储结构,Visit是对结点操作的应用函数 InitStack(S); BiTree p=T; while( ) { if (p) { Visit(p->data); ; p=p->lchild; } else { ; p= ; } } } 六．编写算法（24） 1．试编写统计二叉树中叶子结点个数的算法。（10分） 2．设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法。（14分） 考试科目： 数据结构 共 5页，第 5页

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