《山东专升本数据结构练习1》由会员分享，可在线阅读，更多相关《山东专升本数据结构练习1（10页珍藏版）》请在金锄头文库上搜索。
1、一、填空题：（每小题2 分，共10 分）1. 设有数据结构（D, R）,其中D是数据元素的有限集，R是 的有限集。2. 深度为 k 的二叉树其结点数至多有 个。3. 栈是一种特殊的线性表，它允许在表的一端进行操作。4. 通常象交通、道路问题的数学模型是一种称为的数据结构。5. 哈希表是一种查找表，可以根据哈希函数直接获得。二、单项选择题：（每小题 2 分，共 10 分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用 存储方式最节省运算时间。A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表2.
2、下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序3. 队列的操作原则是 。A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除4. 在具有 n 个结点的二叉链表中，非空的链域个数为 。A. n-1 B. n C. n+1 D. 不确定5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为 。A. O（log2n） B. O（n） C. O（nlog2n） D. O（n2）三、判断题：（每小题2 分，共10 分）判断下列各题是否正确，若正确，
3、在题后的括号内填“T”，否则填“F”。1. 在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（ ）2. 如果有向图 G=（V, E） 的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（）3. 在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（ ）4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ）5. 在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（ ）四、解答下列各题：（每题10分，共40分）1. 已知线性表 L 采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。2. 已知一棵二叉树的先序、中
4、序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。 先序序列是：_ B _ F _ I C E H _ G； 中序序列是：D _ K F I A _ E J C _ ；后序序列是： _ K _ F B H J _ G _ A3. 已知数据表为（48， 70， 33， 65， 24， 56， 12， 92， 86， 22）， a） 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结 果； b） 写出按基数排序思想对最低位进行一次分配和收集的结果。4. 对图1 所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出
5、求解的详细过程示意图）。 图 1 带权无向图五、算法设计题：（前两题必做，每题 15 分，共30分；第三题为附加题，选做， 10 分）1. 已知队列 Q 以循环队列存储。写出 Q 的存储结构类型描述，并试编写算法实现将元素 x 插入队列 Q 的入队操作 EnQueue（Q,x） 和从队列 Q 中获取队首元素的函数 GetTop（Q）。2. 假设线性表L=（al,a2,.,an）用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间， 使得元素的逻辑次序改变为（an,a2,al）。3. 设非空二叉树T采用中序线索二叉链表表示，写出T的存储结构类型描述。试编写算法
6、InOrderTraverse（T）实现对二叉树T的中 序遍历。专升本数据结构试卷2一、单项选择题：（每小题2分，共10分）1. 折半查找法要求查找表中各元素的键值必须是 。A. 递增或递减 B. 递增 C. 递减 D. 无序2. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用 存储方式最节省运算时间。A. 单链表 B. 双链表 C. 仅有头指针的单循环链表 D. 仅有尾指针的单循环链表3. 有64个结点的完全二叉树的深度为一(假设根结点的层次为1)。A. 8 B. 7 C. 6 D. 54. 对于键值序列(2, 33, 21, 18, 65, 38, 7, 49,
7、 24, 86),用筛选法建堆，必须从键值为的结点开始。A. 86 B. 2 C. 65 D. 385. 设图 G 用邻接表存储,则求每个顶点入度的算法时间复杂度为 。A. O(n) B. O(n+e) C. O(n*n) D. O(n*e)二、判断题：(每小题2分,共10分)1. 在队满情况下不能作入队处理,否则,将产生 “ 上溢 ” 。( )2. 基于插入思想的排序算法都是稳定的。( )3. 一个有向图的邻接表和逆邻接表中的结点个数不一定相等。( )4. 若一棵二叉树的任一非叶子结点度为2,则该二叉树为满二叉树。( )5. 广义表是线性表的推广,因此也可以采用顺序方式进行存储。( )三、填
8、空题：(每小题2分,共10分)1. 在单链表中,删除指针 P 所指结点的后继结点的语句是：。2. 有向图 G 用邻接矩阵 A1.n, 1.n 存储表示,其第 i 行的所有元素之和等于顶点 i 的。3. 基数排序算法的时间复杂度为。4. 平衡二叉树中每个结点的平衡因子定义为。5. 利用直接插入排序算法对有 n 个元素的数据表进行排序,在最坏情况下,元素的移动次数为 。四、解答下列各题：(每小题10 分,共40分)1. 写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意图。2. 已知数据表为(60, 20, 31, 5, 44, 55, 61, 30, 80, 150, 4, 29),
9、写出采用希尔排序算法进行排序的详细过程和结果(假设增量 序列 dlta =6,3,1)。3. 已知图 G 的邻接表存储结构示意图如下所示,画出它的逻辑关系示意图,以及按深度优先搜索和广度优先搜索进行遍历所得到的顶 点序列。4. 设散列函数为 H(K) = K mod 5,散列表的地址空间为 0.6,初始时散列表为空,用线性探测法解决冲突,请写出依次插入 23, 14, 9,6. 30, 12, 18时散列地址的计算过程及结果,以及最后得到的散列表。五、算法设计题：(前两题必做,每题15分,共30分；第三题为附加题,选做, 10分)1. 设计算法将一个带头结点的单循环链表A分解为两个具有相同结构
10、的链表B、C,其中：B表中的结点为A表中元素的顺序号为 奇数的结点,而 C 表中的结点为 A 表中元素的顺序号为偶数的结点。(要求利用原表结点。)2. 已知 S 为顺序栈。写出 S 的存储结构类型描述。试编写算法实现将元素 x 插入栈 S 的入栈操作 Push(S,x) 和删除栈顶元素的出 栈操作 Pop(S)。3. 已知一棵完全二叉树存于顺序表 sa 中, sa.elem1.sa.last 包含各结点值。试编写算法根据此顺序存储结构建立该二叉树的二叉链表 T。(专升本)数据结构试题(模 A) 2004-5-1一、单项选择题1. 数据的不可分割的基本单位是。A.元素B.结点C.数据类型D.数据
11、项2下列算法suanfa2的时间复杂度为。int suanfa2(int n) int t=1 ；while(tO)个结点的完全二叉树的深度是。A.elog2(n)uB.elog2(n)+1u C.?log2(n+1)?D.?log2(n)+1?7.与中缀表达式a+b*c-d等价的前缀表达式是。A.+a-*bcdB. *+-abcdC. -+a*bcdD. abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素 37,需依次 与表中元素进行比较,。A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,379.
12、对长度为10 的表作选择(简单选择)排序,共需比较次关键字。A.45 B.90 C.55 D.11010对n个元素的表作快速排序，在最坏情况下,算法的时间复杂度为。A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )11.对长度为10的表作2_路归并排序,共需移动次(个)记录。A.20 B.45 C.40 D.30二、填空(每空 1 分,共 11 分)1. 一个数据结构在计算机中的表示(映象)称为 。2. 线性表中 称为表的长度。3. 栈中元素的进出原则为 。4设数组A1.10,1.8的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素A4,
13、5的存储地址为;若以列序为主序顺序存储,则元素A4,5的存储地址为。5. 一棵深度为6的满二叉树有个非终端结点。6. 若一棵二叉树中有8个度为2的结点,则它有个叶子。7. 顺序查找 n 个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为次, 最多为次;若查找失败,比较关键字的次数为次。8. 对长度为 400的表采用分块(区)查找,最理想的块长为。三、回答下列问题 (每小题5分,共10分)1. 线性表的存储结构,在什么情况下采用顺序结构? 为什么?2. 二叉树有哪几种基本形态? 画图说明之。四、试画出下列存储结构图(每小题4分,共20分)1数组A1.2,0.2的以列序为主序的顺序
14、存储结构。2. 依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。3. 二叉树的顺序存储结构:4. 图的邻接矩阵:5. 有向图的逆邻接表:五、求解下列问题 (每小题6分,共24分)1. 给定 30 个字符组成的电文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D试为字符 A、B、C、D、E、F设计哈夫曼(Huffman)编码。(1) 画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫曼码；(3)计算该树的带权路径长度WPL。2. 试按表( 10,8,9,12,20,5,
15、6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。(1) 试画出插入完成之后的二叉排序树；(2) 若查找元素 17,它将依次与二叉排序树中哪些元素比较大小?(3) 假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。(4) 对该树进行中序遍历,试写出中序遍历序列。3. 试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。T1T2 T3T44. 找出下面网络的最小生成树。六、填空题(在算法中有下划线的位置填空,使之成为完整、正确的算法)算法说明：已知r1.n是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败，则输出”Failure”，返回零；否则输 出”Success”，并返回该记录的序号值。(共8分)算法(C函数)：int bin_search(struct arecord r，int n，k：keytype)/* rl.n为n个记录的递增有序表,k为关键字*/ int
