数据结构期末试题(共103页).doc

《数据结构期末试题(共103页).doc》由会员分享，可在线阅读，更多相关《数据结构期末试题(共103页).doc（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上一、选择题（共30分）1. 数据结构是一门研究非数值计算的程序设计问题中的计算机操作的（ B ）和以及它们之间存在的 （ D）和操作的学科。（1）A数据映像 B数据元素 C逻辑存储 D计算方法（2）A结构 B运算 C算法 D关系2. 在数据结构中，从逻辑上可以将数据结构分为：（ C ）。 A动态结构和表态结构 B 紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构3. 线性表的逻辑顺序和存储顺序总是一致的，这种说法 （ B ）。 A正确 B不正确 4. 算法分析的目的是（ C ），算法分析的两个主要方面是（ A ）。（1）A找了数据结构的合理性 B研究

2、算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性（2）A空间复杂度和时间复杂度 B正确性C可读性和文档性 D数据复杂性和程序复杂性5. 带头结点的单链表head为空的判定条件是 （ B ）。Ahead = NULL Bhead -next = NULLChead - next = head Dhead != NULL6. 非空的循环单链表head的尾结点p应该满足 （ C ）。Ap- next = NULL Bp = NULLCp- next = head Dp = head7. 在一个单链表中，删除p所指的结点的后继结点，则执行语句（ A ）。Ap-next =

3、p-next -next ； Bp=p-next;p-next=p-next-next ； Cp-next= p-next ； Dp=p-next-next；8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 （ D ）。A必须连续 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以9. 对顺序存储的线性表，设其表长为n，且在任何位置插入或删除操作都是等概率的，则插入一个元素平均要移动表中（ B ）个元素。An/2 B(n+1)/2 C(n-1)/2 Dn10. 与单链表相比，双链表的优点之一是（）A插入删除操作更容易 B可以进行随机访问C可以省略头结点指针 D顺序访问相

4、邻结点更灵活11. 栈的特点是（ B ）。插入操作在（）进行，删除操作在（）进行。(1) A先进先出 B先进后出 在栈顶 在栈底 D栈顶或栈底 随机位置12. 一个栈的进栈次序为a,b,c,d,e，则栈不可能的出栈序列是 （ C ）。Aedcba Bdecba Cdceab Dabcde13. 若已知一个栈的进栈序列为1,2,3,4n，其出栈序列为p1,p2,p3,pn，若有p1=n，则pi(1=in)一定为（ ）。Ai Bn Cn-i+1 D不确定14. 已知一棵完全二叉树中共有768个结点，则该树中共有（ B ）个叶子结点。A383 B384 C385 D38615. 先序遍历和中序遍历相

5、同的二叉树为（ D ）。A只有根结点的二叉树 B根结点无左孩子的二叉树C一般二叉树 D只有根结点的二叉树和所有结点只有右子树的二叉树16. 一个有n个顶点的无向图最多有 （ C ）条边。An Bn(n-1) Cn(n-1)/2 D2n17. ( B )的邻接矩阵是对称矩阵。A有向图 B无向图 CAOV图 18. 邻接表是图的（ B ）。A顺序存储结构 B链式存储结构C索引存储结构 D散列存储结构19. 对线性表进行二分查找时，要求线性表必须（ C ）。A以顺序方式存储 B以链接方式存储C以顺序方式存储且结点按关键字有序排列D以链接方式存储且结点按关键字有序排列20. 采用顺序查找方法查找长度为

6、n的线性表时，每个元素的平均查找长度为（ C ）。An Bn/2 C(n+1)/2 D(n-1)/221. 有一个有序序列（1,2,3,4,5,6），当用二分法进行查找值为4的结点时，经过（ C ）次比较后查找成功。A1 B2 C3 D422. 二叉树的第i层最多有（ C ）个结点。 A2i B2i C2i-1 D2i-123. 在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。 A1/2 B1 C2 D424. 一个无向连通图（）最小生成树。A只有一棵 B一棵或多棵 C一定有多棵 D不一定有25. 一个图的（）表示法是唯一的，而（）表示法是不唯一的。A三元组 B邻接矩阵 C邻接表 .

7、 索引二、选择题（每空1分，共30分）1. 线性结构中元素之间存在 的关系，树形结构中的元素之间存在 的关系，图形结构中的元素之间存在 的关系。2. 算法的五个特点是： ， ， ， ， 。3. 栈是限定仅在表尾进行 操作的线性结构。表头一端称为 ，表尾的一端称为 。4. 队列是限定仅在表尾进行 和在表头进行 的线性表，其特点是： 。5. 如有如下顺序栈的定义#define MAXSIZE 500Typedef struct char dataMAXSIZE;int top;sqstack;sqstack ss;则栈空的条件是 ，栈满的条件是 ，栈顶元素的表 达式是 ，栈底元素的表达式是 。6.

8、 在一个长度为 n的向量的第i个元素（1=i=n）之前插入一个元素时，需向后移动的元素个数数为 。7. 在双链表中，每个结点都有两个指针域，一个指向 ，另一个指向 。 8. 数据的逻辑结构包括 ， ， ， 四种类型；其中 和 统称为非线性结构。9. 数据的存储结构分为 和 。其中要求逻辑上相邻的元素物理上也相邻的存储方式为 。 三、简答题(每小题分，共分)1. 下列程序段的时间复杂度是 O（mn） 。 for ( i = 0 ; i n ; i+ )for( j = 0 ; j next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL;

9、 p=HL; D. HL=p; p-next=HL;3. 3. 对线性表，在下列哪种情况下应当采用链表表示？(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4. 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV网是一种（ D ）。 A有向图 B无向图 C无向无环图 D有向无环图6. 6. 采用开放定址法处理散列表的冲突时，其平均查找长度（ B）。A低于链接法处理冲突 B. 高于链接法处理冲突

10、 C与链接法处理冲突相同 D高于二分查找7. 7. 若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。A值 B函数 C指针 D引用8. 8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A）。A行号 B列号 C元素值 D非零元素个数9. 9. 快速排序在最坏情况下的时间复杂度为（ D）。AO(log2n) BO(nlog2n) C0(n) D0(n2)10. 10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 运算题（每题 6 分，共24分）1. 1.

11、数据结构是指数据及其相互之间的联系。当结点之间存在M对N（M：N）的联系时，称这种结构为_图_。2. 2. 队列的插入操作是在队列的_尾_进行，删除操作是在队列的_首进行。3. 3. 当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件是_top=0_(要超出才为满)_。4. 4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O(1)_，在表尾插入元素的时间复杂度为O(n_。5. 5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用128_个字节。W中第6 行的元素和第4 列的元

12、素共占用_44_个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W6，3的起始地址为108_。6. 6. 广义表A= (a,(a,b),(a,b),c),则它的深度为_3_，它的长度为_3_。7. 7. 二叉树是指度为2的_有序_树。一棵结点数为N的二叉树，其所有结点的度的总和是_n-1_。8. 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列_。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_后缀表达式_。9. 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中n-1_个用于指向孩子_n+1个

13、指针是空闲的。10. 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A0中。其余类推，则A i 元素的左孩子元素为2i+1_,右孩子元素为_2i+2_，双亲元素为_(i-1)/2。11. 11. 在线性表的散列存储中，处理冲突的常用方法有_开放定址法_和_链接法_两种。12. 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用_排序。三、 三、 运算题（每题6分，共24分）1. 1. 已知一个65稀疏矩阵如下所示，试：（1） （1） 写出它的三

14、元组线性表；（2） （2） 给出三元组线性表的顺序存储表示。2. 2. 设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。四、 四、 阅读算法（每题7分，共14分）1. 1. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; (1) (1) 指出该算法的功能；(2) (2) 该算法的时间复杂度是多少？2. 2. 写出下述算法的功能： void AJ(adjlist GL, int i, int n)

15、Queue Q; InitQueue(Q); coutiadjvex; if(!visitedj) coutjnext; 五、 五、 算法填空（共8分）如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下标 else if (Kmid.key) _; /在左子表上继续查找 else _; /在右子表上继续查找return -1; /查找失败，返回-1

16、六、 六、 编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法。ElemType DeleFront(LNode * & HL)参考答案一、 一、 单选题（每题2分，共20分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C二、 二、 填空题（每空1分，共26分）1. 1. 联系 图（或图结构）2. 2. 尾 首3. 3. top=04. 4. O（1） O（n）5. 5. 128 44 1086. 6. 3 3 7. 7. 65515132-145-2515637 图7有序 n-18. 8. 有序序列 后缀表达式（或逆波兰式）9. 9. 2n n-

17、1 n+110. 10. 2i+1 2i+2 (i-1)/211. 11. 开放定址法 链接法12. 12. 快速 归并三、 三、 运算题（每题6分，共24分）1. 1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元组线性表的顺序存储表示如图7示。2. 2. 图8如图8所示。3. 3. DFS： BFS： 4. 4. 拓朴排序为： 4 3 6 5 7 2 1 四、 四、 阅读算法（每题7分，共14分）1. 1. (1) 判断n是否是素数（或质数） （2）O（）2. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的

18、图。五、 五、 算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、 六、 编写算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr空表next;ElemType temp=p-data;delete p;return temp; 一、 一、 单选题（每题 2 分，共20分）1. 1. 栈和队列的共同特点是( A )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 2. 2. 用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针

19、都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改3. 3. 以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树4. 4. 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 A688 B678 C692 D6965. 5. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6. 6. 二叉树的第k层的结点数最多为( ). A2k-1 B.2K+1

20、C.2K-1 D. 2k-17. 7. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，38. 8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A1 B2 C3 D410. 10. 设有6个结点的无向图，该图

21、至少应有( )条边才能确保是一个连通图。A.5 B.6 C.7 D.8二、 二、 填空题（每空1分，共26分）1. 1. 通常从四个方面评价算法的质量：_、_、_和_。2. 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。3. 3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_个，树的深度为_，树的度为_。4. 4. 后缀算式9 2 3 +- 10 2 / -的值为_。中缀算式（3+4X）-2Y/3对应的后缀算式为_。5. 5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种

22、存储结构中，n个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。6. 6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_个和_个。7. 7. AOV网是一种_的图。8. 8. 在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。9. 9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_、_、_和_。10. 10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高

23、度_。11. 11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。12. 12. 在快速排序、堆排序、归并排序中，_排序是稳定的。三、 三、 运算题（每题 6 分，共24分）1. 1. 在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 2. 图10请画出图10的邻接矩阵和邻接表。3. 3. 已知一个图的顶点集V和边集E分别为： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10

24、,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4. 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、 四、 阅读算法（每题7分，共14分）1. 1. LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； retur

25、n L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。2. 2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if六、 六、 编写算法（共8分）统计出单链表HL中结点的值等于给定值X的

26、结点数。 int CountX(LNode* HL,ElemType x)参考答案一、 一、 单选题（每题2分，共20分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A二、 二、 填空题（每空1分，共26分）1. 1. 正确性 易读性 强壮性 高效率2. 2. O(n)3. 3. 9 3 34. 4. -1 3 4 X * + 2 Y * 3 / -5. 5. 2n n-1 n+16. 6. e 2e7. 7. 有向无回路8. 8. n(n-1)/2 n(n-1)9. 9. （12，40） （ ） （74） （23,55，63）10. 10. 增加111. 1

27、1. O(log2n) O(nlog2n)12. 12. 归并三、 三、 运算题（每题6分，共24分）1. 1. 线性表为：（78，50，40，60，34，90）2. 2. 邻接矩阵： 邻接表如图11所示：图113. 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 见图124444422255285283452843图12四、 四、 阅读算法（每题7分，共14分）1. 1. （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,an,a1） 2. 2. 递归地后序遍历链式存储的二叉树。五、 五、 算法填空（每空2分，共8 分）true BST-left BST-right 六、 六、 编写算法（8分）int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i为计数器 while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循环时i中的值即为x结点个数 return i; /CountX 一、 一、