数据结构试题样题及答案

1、数据结构试题样题及答案一、单项选择题（每小题 2分，共30分）1. 数据结构中，与所使用的计算机无关的是数据的（）结构。A.逻辑 B. 物理 C. 存储 D.逻辑与物理2. 下述各类表中可以随机访问的是（）。A. 单向链表B. 双向链表 C.单向循环链表D.顺序表3. 在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。A. 21 B.20 C. 19 D. 254. 元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45. 一个队列的入队序列是 5，6，7，8,则队列

2、的输出序列是（）。A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情况6. 串函数 StrCmp （“d”，“D'）的值为（）。A . 0B. 1C . -1D. 37. 在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A. p=q nextB. p next=qC. p next=q next D. q next=NULL8. 设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。A. 2*n-1 B. 2*n +1 C. 2*n D. 2*（ n-1）9. 对如图1所示二叉树进行中序

3、遍历，结果是（）。A. dfebagc B. defbagc C. defbacg D.dbaefcg图110 .任何一个无向连通图的最小生成树（）。A.至少有一棵 B.只有一棵C. 一定有多棵 D. 可能不存在11. 设有一个10阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主 序存储到一维数组 B中（数组下标从1开始），则矩阵中元素 A8,5在一维数组B中的下标是 （ ）。A. 33B . 32C. 85D . 4112 . 一组记录的关键字序列为（37, 70, 47, 29, 31, 85）,利用快速排序，以第一个 关键字为分割元素，经过一次划分后结果为（）。A. 31,

4、 29, 37, 85, 47, 70B. 29, 31, 37, 47, 70, 85C. 31, 29, 37, 70, 47, 85D. 31, 29, 37, 47, 70, 8513 .对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元 素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（）。A. 原序列是升序排列B. 原序列是降序排列C. 对序列只进行了 2趟冒泡D. 对序列只进行了 3趟冒泡14. 在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行 （）°A.x=top->data;

5、top=top->n ext;B. top=top->next ; x=top;C.x=top;top=top->n ext ;D. x=top->data;15. 串函数StrCat （a,b）的功能是进行串（）°A .比较B .复制C.赋值D .连接二、填空题（每小题2分，共24分）1 .在一个单向链表中p所指结点之后插入一个s所指的新结点，应执行 s->n ext=p->n ext ;禾口操作。2根据数据元素间关系的不同特性，通常可分为 、四类基本结构。3. 在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为 °（结

6、点的指针域为n ext）4. 遍历二叉排序树可得到一个有序序列。5. 一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个叶结点。6. 如图1所示的二叉树，其中序遍历序列为_一。7. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的 、禾廿三项信息。8 .有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82的结点，经次比较后查找成功。9 .图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是 的。（回答正确或不正确)10. 哈希法既是一种存储方法，又是一种 。11. 44.在对一组记录(55,

7、39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较 次。12. 栈和队列的操作特点分别是 和 。三、综合题(每小题10分，共30分)1. 已知序列11 , 19, 5, 4, 7, 13, 2, 10,(1) 试给出用归并排序法对该序列作升序排序时的每一趟的结果。(2) 对上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉树描述建堆过程)。2. 设有序表为(13, 19, 25, 36, 48, 51, 63, 84, 91, 116, 135, 200),元素的下标依次为1,2,12.(1) 说出有哪几个元素需要经过3

8、次元素间的比较才能成功查到(2) 画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)(3) 设查找元素5,需要进行多少次元素间的比较才能确定不能查到3.(1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树(2) 说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序 遍历的结果四、程序填空题(每空 2分，共16分)1. 以下冒泡法程序对存放在a1 , a2,an中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程序按升序排列。Void bsort (NODE a , i nt) NODE temp;int i

9、,j,flag;for(j=1; (1);j+);flag=0;for(i=1;(2);i+)if(ai.key>ai+1.key) flag=1;temp=ai;(3) ;(4) ;if(flag= =0)break;程序中flag 的功能是 7.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分 (树结构中左、右指针域分别为left和right，数据域为data,其数据类型为字符型，BT指向根结点)。4Void Postorder (struct BTree Node *BT) if(BT!=NULL)(1) ;(2) ;(3);试题答案；一、单项选择题（每小题 2分，共3

10、0分）10 . A1. A 2 . D 3 . B 4 . B 5 . A 6 . C11. A 12 . D 13 .D 14 . A 15 . D2分，共24分）二、填空题（每小题1. p->n ext=s;图状2. 集合、线性、树形、3. f=f->next;4. 中序5. n6. dgbaechhif7. 行号、列号、元素值8.4次9. 正确10. 查找方法11. 3 次12. 先进后出先进先出三、综合题（每小题 10分，共30 分） 1 .（1）初始第一趟第二趟第三趟11, 19, 5, 4, 7, 13, 2, 10 11 , 194 , 57 ,4, 5,2, 4,11, 192 ,5, 7,10,132 , 107, 10, 1311, 13, 1919111013(1)13,36,63,135(3)3 次(1)111913151010（2）中序遍历中序 2，3， 4，5，6，7，14，16，18