《数据结构》试卷七.doc

《数据结构》试卷七 一、填空题：(共20分) 1、数据对象指具有 的数据元素集合。 2、TAIL(HEAD((a,b),(c,d))))= 。 3、二维数组存储地址计算公式(以行序为主)为 (b为基地址，每个元素占存储单元数为l，下标取值范围为(c1,d1),(c2,d2))。 4.一个连通图的生成树是一个 . 5、顺序存储结构下，当 时表示栈空。 6、二叉树结点的度 2,且树中子树有左右之分，不能颠倒，故二叉树是一 棵 树。 7、高度为Ｋ的二叉树中至多有 个结点。 8、对树的遍历有 两种。 9.对长度为12的有序表进行折半查找,等概率时查找成功的平均查找长度为 . 10、 ○ 如图，树中叶子结点中的数值即该结点的权值，树的带权路径长度、树的 / ＼ 路径长度分别为 。 ① ○ / ＼ ② ○ / ＼ ③ ④ 二、选择题：(共２０分) 1、下面关于线性表的叙述中，错误的是（ ） （A）线性表采用顺序存储，必顺占用一片连续的存储单元。 （B）线性表采用顺序存储，便于进行插入和删除操作。 （C）线性表采用链接存储，不必占用一片连续的存储单元 （D）线性表采用链接存储，便于插入和删除操作。 2、编号为1,2,3,4的四辆列车，顺序开进一个栈式结构栈台，则开出栈台顺序有( )种。 (A) 1 (B) 3 (C) 5 (D) 7 3、将n个元素的顺序表倒置，则至少需要的附加空间为( ) (A)0 (B)1 (C)n (D)n+1 4、n=1000，要求最快，且最省内存的排序方法为（ ） (A)快速排序 (B)shell排序 (C)归并排序 (D)堆排序 5、在构造散列表时，下面能采用的处理冲突的方法为( ) (A)开放定址法 (B)链地址法 (C)直接定址法 (D)再hash法 6、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 7、在下列存储形式中，哪一个不是树的存储形式 A）双亲表示法 B）孩子链表表示法 8、以下哪一个不是队列的基本运算? （A）从队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值 9、下面关于图的存储的叙述中正确的是 （A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 对线性表进行二分法查找，其前提条件是 A）线性表以顺序方式存储，并且按关键码值排好序 B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以链接方式存储，并且按关键码值排好序 D）线性表以链接方式存储，并且按关键码值的检索频率排好序 I ２、画出下列无向图的邻接表存储结构，并由邻接表写出广度优先有哪些信誉好的足球投注网站序列和深度优先有哪些信誉好的足球投注网站序列： A ／│＼ B─C─D ＼│／ E ３、用快速排序法对下列整数序列进行排序，写出中间与最后结果。 [89,27,52,80,15,28,100,72] ４、如图所示的５阶B-树，试画出插入96后B-树的形状。 30 50 70 90 ┌───┐ ┌───┐┌────┐┌──────┐┌────