“数据结构”期末考试试题
一、 单选题(每小题2分，共12分) 1 ?在一个单链表HL中，若要向表头插入一个由指针 A ? HL = ps p 一＞next = HL B ? p 一＞next = HL; HL= p3 C ? p 一＞next = Hl ; p = HL;
D ? p 一＞next = HL 一 ＞next;HL 一＞next = p; 2 ? n个顶点的强连通图中至少含有 ()。 A.n —I条有向边 B.n 条有向边 C.n(n — 1) /2条有向边 D.n(n — 1)条有向边
p指向的结点，则执行()。
3. 从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 ()。 A.0(1) B.O(n)
C.O(1Ogzn) D.O(n2)
4. 由权值分别为3，8，6，2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 ()。 A ? 24 B ? 48
C. 72 D ? 53
5 ?当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为 ()参数，以节省参数值的传
输时间和存储参数的空间。 A.整形 B.引用型
C.指针型 D.常值引用型?
6 ?向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为 ()。 A ? O(n) B ? 0(1)
C ? O(n2) D ? O(10g2n)
二、 填空题(每空1分，共28分)
1 ?数据的存储结构被分为 、 、 和 四种。 2 ?在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为一一域和一一域。
3 ? 中缀表达式 3十x*(2.4 / 5—6)所对应的后缀表达式为 。 4 ?在一棵高度为h的3叉树中，最多含有一一结点。
5 ?假定一棵二叉树的结点数为 18,则它的最小深度为一一，最大深度为—— 6 ?在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定一一该结点的值， 右子树上所有结点的值一定一一该结 点的值。 7 ?当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层 -- 调整，直到被调整到 --- 位置为止。
8 ?表示图的三种存储结构为 、 和 。 9 ?对用邻接矩阵表示的具有 n个顶点和e条边的图进行任一种遍历时，其时间复杂度为一一，对用邻接表表示的图进行任一 种遍历时，其时间复杂度为 。
10 ?从有序表(12，18，30, 43, 56，78，82，95)中依次二分查找 43和56元素时，其查找长度分别为一一和 ------------- ?假定对长度n= 144的线性表进行索引顺序查找，并假定每个子表的长度均为 ，则进行索引顺序查找的平均查找长 度为一一，时间复杂度为——
12 ? 一棵B—树中的所有叶子结点均处在一一上。
13 ?每次从无序表中顺序取岀一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑
选岀一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做一一排序。
14 ?快速排序在乎均情况下的时间复杂度为一一，最坏情况下的时间复杂度为一一。 三、运算题(每小题6分，共24分) 1 ?假定一棵二叉树广义表表示为 a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序：
中序； 后序： 2 ?已知一个带权图的顶点集 V和边集G分别为： V = {0，1，2, 3，4, 5}；
E={(0 , 1)8 , (0 , 2)5 , (0 , 3)2 , (1 , 5)6 , (2 , 3)25 , (2 , 4)13 , (3 , 5)9 , (4 , 5)10}, 则求岀该图的最小生成树的权。 最小生成树的权；
11 3
?假定一组记录的排序码为(46 , 79, 56, 38, 40, 84, 50, 42)，则利用堆排序方法建立的初始堆为一一。
4 ?有7个带权结点，其权值分别为 3, 7, 8, 2, 6, 10, 14,试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径 长度、高度、双
分支结点数。
带权路径长度：一一 高度：一一 双分支结点数：一一。 四、阅读算法，回答问题(每小题8分，共16分) 1 ? VOIdAC(List&L)
{
InitList(L) ；
InsertRear(L;25) ；
lnsertFront(L , 50)
lntaL4] = {5 , 8, 12, 15, 36}; for(inti = 0; i<5; i++)
%2== 0)InsertFront(L , a[i])；
elselnsertRear(L , a[i])；
if (a[i] }
该算法被调用执行后，得到的线性表
2 {
InitQueue(Q) ；
inta[5] = {6 , 12, 5,15, 8}; for(int i QInsert(Q QInsert(Q QInsert(Q
L为：
. void AG(Queue&Q)
= 0;i<5; i++)QInsert(Q , a[i])； , QDelete(Q))； , 20)；
, QDelete(Q)十 16)；
while(!QueueEmpty(Q))cout 该算法被调用后得到的输岀结果为： 五、 算法填空，在画有横线的地方填写合适的内容 (每小题6分，共12分) 1 .从一维数组A[n)中二分查找关键字为 K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一 IntBinsch(ElemTypeA[] , Intlow , int high , KeyTypeK) { if(low< { int mid 1。 = high) = (low+high) /2； if(K = = A[mid].key)——； else if (K else return — l ； } 2 --- ； ； .已知二叉树中的结点类型 BinTreeNode定义为： BT中值为x的结 structBinTreeNode{ElemType data ； BinTreeNode*left , *right}； 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树 点所在的层号，请在划有横线的地方填写合适内容。 Int NodeLevel(BinTreeNode * BT , ElemType X) { if(BT : = NULL)return 0 ; //空树的层号为 0 else if(BT 一 >data = = X)return 1; //根结点的层号为 //向子树中查找x结点 else{ int cl = NodeLevel(BT 一 >left , X); if(cl> = 1)return cl+1; int c2 = if 1 ； ； //若树中不存在X结点则返回o else return 0 ； } } 六、 编写算法(8分) 按所给函数声明编写一个算法， 从表头指针为HL的单链表中查找岀具有最大值的结点， 则中止运行。 EIemType MaxValue(LNOde*HL); 若单链表为空 该最大值由函数返回, “数据结构”期末考试试题答案 一、 单选题（每小题2分，共12分） 评分标准；选对者得2分，否则不得分。 1 . B 2 . B 3 . C 4 . D 5 . B 二、 填空题（每空1分，共28分） 1 ?顺序结构 ~2~.值(或 data) 3 4 5 6 7 8 9 链接结构 索引结构 子表指针(或sublist) . 3 x 2 . 4 5 / 6 一 * 十 . (3h— 1) / 2 . 5 18 ?小于 .向上 ?邻接矩阵 . O(n2) 0(e) 大于(或大于等于) 堆顶 邻接表 边集数组(次序无先后) 10 . 1 3 11 . 13 O( 12 .同一层 13 .插人 选择 14 . O(nlog 2n) O(n 2) ) 三、运算题(每小题6分，共24分) 1 .先序：a, b, c, d, e, f, e // 2 分 中序：c, b, d, a, f, 8, e 后序：c, d, b, e, f, e, a //2 分 //2 分 // 6分 // 6 分 // 3分 2 .最小生成树的权：31 3 4 . (84 , 79, 56, 42, 40, 46, 50, 38) ?带权路径长度：131 高度：5 // 2分 // 1分 双分支结点数：6 四、 阅读算法，回答问题(每小题8分，共16分) 评分标准：每小题正确得 8分，岀现一处错误扣4分，两处及以上错误不得分。 1 2 1 . (36 , 12, 8, 50, 25, 5, 15) . 5 15 8 6 20 28 (每小题6分，共12分) 五、 算法填空，在画有横线的地方填写合适的内容 . feturn mid // 2 分 returnBinsch(A , low, mid 一 1, K) // 2 分 returnBmsch(A , mid+1 , high , K) // 2 分 2 . NodeLevel(BT — >right , X) // 3 分 // 3 分 (c2>=1)returnc2 十 1 六、 编写算法(8分) 评分标准：请参考语句后的注释，或根据情况酌情给分。 ElemType MaxValue(LNodeO* HL 。) { if (HL = =NUlL){ // 2 分 ” < cerr?\ exit(1) ； } ElemTypemax : HL一 >data ; LNOde*p=HI — >next ; while(P! : NULL){ // 7 分 // 3 分 // 4 分 if(max data)max = p 一 >data ； p = p 一 >next ； } returnmax ； } // 8 分 数据结构复习资料 6 . A 一、填空题 散列结构（次序无先后） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 2. 数据结构被形式地定义为（D, R ）,其中D是 3. 操作对象 以及它们之间的 关系 关系 和运算等的学科。 有限集合。 数据元素 的有限集合,R是D上的 逻辑结构 数据结构包括数据的 、数据的存储结构 和数据的 运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 _线性结构 _和_非线性结构 _。 一对多关系，图形结构中元素之间存在 多对多关系。 5. 线性结构中元素之间存在 一对一关系，树形结构中元素之间存在 6. 在线性结构中，第一个结点 _没有—前驱结点，其余每个1个前驱结点；最后一个结点 _没有_ 后续结点， 其余每 结点有且只有 个结点有且只有 1个后续结点。 7. 在树形结构中，树根结点没有 —前驱—结点，其余每个结点有且只有 _1_个前驱结点；叶子结点没有 _后续_结点，其 余每个结点的后续结点数可以任意多个_。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 9. _任意多个 _。 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序、链 式、索引和散列。 10. 数据的运算最常用的有 5种，它们分别是 插入、删除、修改、 查找、排序。 11. 一个算法的效率可分为 _时间 _____ 效率和 _空间_效率。 12. 在顺序表中插入或删除一个元素， 需要平均移动_表中一半元素，具体移动的元素个数与 _表长和该元素在表中的位置 _有关。 13. 线性表中结点的集合是—有限_的，结点间的关系是 _一对一_的。 14. 向一个长度为n的向量的第i个元素（1 < i < n+1）之前插入一个元素时，需向后移动 15. 向一个长度为n的向量中删除第i个元素（1 < i < n）时，需向前移动 n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 17. 0（1） _，因此，顺序表也称为_随机存取_的数据结构。 _n-i+1 —个元素。 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元 素的物理位置 不一定相邻。 _其直接前驱结点的链域的值 _指示。 18?在单链表中，除了首元结点外，任一结点的存储位置由 19. 0（n）。 在n个结点的单链表中要删除已知结点 *p，需找到它的前驱结点的地址，其时间复杂度为 20. 向量、栈和队列都是—线性 _结构，可以在向量的 _任何 __________ 位置插入和删除元素；对于栈只能在 _栈顶_插入和删除 元素；对于队列只能在 _队尾 _______ 插入和_队首_删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 _栈顶_。不允许插入和删除运算的一端称为 _____________ 栈底 ____ 。 22. ____ 队列_是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. _不包含任何字符（长度为0）的串_称为空串； _ 由一个或多个空格 （仅由空格符）组成的串 ______________ 称为空白串。 24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。 25. 假设有二维数组 Ax8，每个元素用相邻的6个字节存储，存储器按字节编址。已知 A的起始存储位置（基地址）为 1000，则 数组A的体积（存储量）为 288 B ;末尾元素鶴的第一个字节地址为 1282 ;若按行存储时，元素 的第一个字 。 节地址为（8+4） X 6+1000=1072 ;若按列存储时，元素 A47的第一个字节地址为 （6 X 7+ 4） X 6 + 1000）= 1276 26. 27. 由3个结点所构成的二叉树有 _5_种形态。 一棵深度为6的满二叉树有_m+n2=0+ n2= n°-1=31 _个分支结点和_26-1 =32_个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 28. 一棵具有2 5 7个结点的完全二叉树，它的深度为 _9 。 +1=9 （注：用[log 2（n） +1= |l_8.xx 29. 设一棵完全二叉树有 700个结点，则共有_ 350 _个叶子结点。 答：最快方法：用叶子数=[n/2] = 350 30. _________________________ 设一棵完全二叉树具有 1000个结点，则此完全二叉树有 _500_个叶子结点，有 _499_个度为2的结点，有 _ 1_ 个结 点只有非空左子树，有_0 个结点只有非空右子树。 答：最快方法：用叶子数=[n/2] = 500，n2=n。-仁499。另外，最后一结点为 2i属于左叶子，右叶子是空的，所以有 1个非空 左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数= 31. 0. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 _顺序查 找（线性查找） _。 k,用二分法检索表中与 k相等的元素，在查找不成 _7_。 32. 线性有序表（a, a?, a3，…，矗6）是从小到大排列的，对一个给定的值 功的情况下，最多需要检索 _8 _次。设有100个结点，用二分法查找时，最大比较次数是 33. 假设在有序线性表 a[20]上进行折半查找，则比较一次查找成功的结点数为 1;比较两次查找成功的结点数为 _ 2_ ;比较 四次查找成功的结点数为 _ 8 _ ;平均查找长度为 3.7_。 解：显然，平均查找长度= 0 （log 2n） <5次（25）。但具体是多少次，则不应当按照公式 ASL =\+1 Iog2(n +1)来计算(即(21 X log 221) /20 =4.6次并不正确！)。因为这是在假设 n = 2-1的情况下推导出来的公式。 n 应当用穷举法罗列： 全部元素的查找次数为=(1 + 2X 2+ 4X 3+ 8X 4 + 5X 5 )= 74; ASL = 74/20=3.7 34. 折半查找有序表(4, 20 ____ 比较大小。 35. 在各种查找方法中，平均查找长度与结点个数 n无关的查找方法是 6, 12, 20, 28 , 38, 50, 70, 88, 100),若查找表中元素 !!! 20，它将依次与表中元素 28 , 6, 12, 散列查找 _。 36. 散列法存储的基本思想是由 _关键字的值 ________ 决定数据的存储地址。 二、判断正误(在正确的说法后面打勾，反之打叉) (X ) 1.链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分另U存放多个指针。例如，双向链表中的结点可以含有两个指针域，分另U存放指向其 直接前趋和直接后继结点的指针。 (X ) 2.链表的物理存储结构具有同链表一样的顺序。 错，链表的存储结构特点是无序， 而链表的示意图有序。 错，链表的结 (X ) 3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 点不会移动，只是指针内容改变。 (X ) 4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 (X ) 5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” (X ) 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为 插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 (X ) 7.线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 (X ) 8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 (X ) 9.顺序存储方式只能用于存储线性结构。 n的顺序表中， 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储 方式是顺序存储方式。(后一节介绍) (X ) 10.线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。 (X ) 11.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 (X ) 12.在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用， CPU中也用队列。 (V ) 13.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先岀型结构。 (V ) 14.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 (X ) 15.栈和链表是两种不同的数据结构。
大学数据结构期末考试试题(有答案)
