《考研真题：广东暨南大学2022年[数据结构]考试真题》由会员分享，可在线阅读，更多相关《考研真题：广东暨南大学2022年[数据结构]考试真题（9页珍藏版）》请在金锄头文库上搜索。
1、考研真题：暨南大学 2022 年数据结构考试真题考研真题：暨南大学 2022 年数据结构考试真题一、单项选择题一、单项选择题1.下述关于顺序存储结构优点的说法，哪个是正确的（）A.插入运算方便B.可方便地用于各种逻辑结构的存储表示C.存储密度大D.删除运算方便2.假设根结点为第 1 层，深度为 h 层的二叉树至少有（）个结点(h1)；A.2hB.2h-1C.2h+1D.2h-13.用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是（）A.入栈操作的复杂度为 O(1)B.出栈操作的复杂度为 O(1)C.删除底部元素的复杂度为 O(1)
2、D.插入一个新的堆栈底部元素复杂度为 O(1)4.以下关于递归算法的论述，不正确的是（）A.递归算法的代码可读性好B.递归算法可以提高程序运行效率C.递归调用层次太深有可能造成堆栈溢出D.递归调用层次太深会占用大量内存5.设有字符集合4,6,3,W,S，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生在任何时刻。则以下的出栈序列错误的是（）。A.64WS3B.4W36SC.6W34SD.WS4366.在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。A有向图B无向图C树D矩阵7.具有 k 个顶点的完全有向图的边数为（）。A.k(k-1)B.k(k-1)/2C.k2-1
3、D.k2+18.若线性表最常用的操作是增加或者删除某个元素,则采用（）存储方式节省时间.A.单链表B.双链表C.单循环链表D.顺序表9.由权为 6,3,2,8 的四个叶子结点构造一个哈夫曼树，该树带权路径长度为（）。A.36B.35C.34D.3310.为了提高哈希表的查找效率，以下方法说法不正确的是（）。A.设计好的哈希函数B.增加哈希函数的个数C.增大存储空间D.采用更好的地址冲突解决方法11.以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树12.对于一个整数集合11，37，29，55，80，46，73，17进行散列存储时，若选用函数 H（K）=K%9 作为散列(哈
4、希)函数，则散列地址为 1 的元素有（）个。A3B4C5D613.有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3个字节，则用三元组表示该矩阵时，总共需要的存储空间为（）字节。A30B33C90D9914.在一个双向链表中，当删除结点 p 时，错误的操作序列为（）。A.p=p-prev;p-next-prev=p;p-next=p-next-next;B.p=p-next;p-prev=p-prev-prev;p-prev-next=p;C.p-prev-next=p-next;p-next-prev=p-prev;D.p=p-prev;p-next=p-
5、next-next;p-next-prev=p;15.在一个具有 V 个顶点的有向连通图中，若所有顶点的入度数之和为 N，所有顶点的出度之和为 M，则以下说法正确的是（）。AV=(M+N)/2BMVCM=NDNV二、填空题二、填空题1.对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 。2.在单链表中，要将 m 所指结点插入到 n 所指结点之后，其语句表示为 。3.设有数组 Aij，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A58的存储首地址为 。4.设哈夫曼树中有 199
6、个结点，则该哈夫曼树中有 个叶子结点。5.对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较 次关键字，至少需要比较 次关键字。6.由 3 个结点可以构造出 种不同的二叉树。7.最大容量为 s 的循环队列，队尾指针是 rear，队头是 front，则队满的条件是 。8.G 是一个非连通无向图，共有 28 条边，则该图至少有 个顶点。9.数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用 排序算法最节省时间。三判断题三判断题1.对 n 个记录进行插入排序，最多只需要 O(nlog(n)次两两比较。()2.用链表(Linked list)来实现的堆栈，单次
7、入栈/出栈操作的时间复杂度可达到O(1)。()3.当图 G 中存在权重为负数的边时，Dijkstra 算法不能用于计算 G 中两结点间最短路径。()4.贪婪算法有时候能够求出全局最优解，有时候无法求出全局最优解。()5.对含有 n 个记录的集合进行快速排序，在最坏情况下的时间复杂度是O(nlog(n)。()6.哈希表查找效率高，当查找主键在范围a,b内所有的记录时，也应该优先选择哈希表。()7.无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵以节省存储空间。()8.用 Prime 算法和 Kruskal 算法求得的图的最小生成树一定相同。()9.在一个有向图的邻接表或逆邻接表中，若某顶点的
8、链表为空，则该顶点的度为零。()10.在有 n 个顶点的无向图中，若边数n-1，则该图必是连通图。()四、简答题四、简答题1.简述逻辑结构的四种基本关系并画出它们的关系图。（10 分）2.设二维数组 num1.m,1n含有 m*n 个整数，请分析判断数组中元素是否互不相同的算法的时间复杂度。（8 分）3.设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，请写出二路归并排序的方法下，每趟排序结束后关键字序列的状态。（6 分）4.已知图 1 所示的有向图，请给出（1）每个顶点的入度与出度；（2）邻接矩阵。（10 分）5.在一棵空的二叉排列树中依次插入关键字序列为 12
9、，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排列树。（6 分）五、算法填空五、算法填空1.在汉诺塔(hanoi tower)游戏中，总共有 3 根柱子和 n 个大小不一样的盘子。初始状态时 n 个盘子从小到大堆叠在 1 号柱子，下面的递归算法伪代码能够将这n 个盘子从 1 号柱子移动到 3 号柱子。其中，该递归算法满足以下条件：(1)每次只移动 1 个盘子，(2)任何一个盘子只有当它上面没有堆放盘子时才能移动，(3)图 1.有向图任何时刻在任何一个柱子上永远不能出现大盘子堆在小盘子之上的情况。请在_处填上适当内容，使其成为一个完整的算法。hanoi(from,tmp,to
10、,n)if(n=1)move(1),(2);return;hanoi(3);printf(%d,%d),from,to);hanoi(4);return;2.假设一维数组 A 保存有 N 个整数，以下快速排序算法代码能够对数组 A 进行排序。请在_处填上适当内容，使其成为一个完整的算法。intpartition(int*A,intN,intp,intr)intx=Ar;inti=(5);for(intj=p;j=r-1;j+)if(6)i=i+1;inttemp=Ai;Ai=Aj;Aj=temp;inttemp=Ai+1;Ai+1=Ar;Ar=temp;return(7);voidQuickS
11、ort(int*A,intN,intp,intr)intq;if(8)q=partition(A,N,p,r);QuickSort(9);QuickSort(10);return;voidmain()QuickSort(A,N,0,N-1);return0;六编写算法（30 分）六编写算法（30 分）1.写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为 A-Z 这 26 个字母与 0-9 这 10 个数字）。（10 分）2.已知 f 为单链表的表头指针，链表中存储的都是整型数据，请写出实现下列运算的递归算法，求：（1）链表中最大整数；（2）所有整数的平均值。（10 分）3.采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径。（10 分）
