当前位置：文档之家 › 数据结构(本)期末综合理解练习(2015年度11月)

数据结构(本)期末综合理解练习(2015年度11月)

  • 格式：doc
  • 大小：235.29 KB
  • 文档页数：46

. 数据结构（本）期末综合练习

2015年11月 综合练习一 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( C )个元素。 A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的 三元组表共有6个元素，矩阵A共有( C )个零元素。 A．8 B．72 C．74 D．10 3.字符串( A )是“abcd321ABCD”的子串。 A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段 char a[ ]=“abdcacdef”; char *p=a; int n=0; while( *p!=‘\0’){ n++; p++;} 结果中,n的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.栈和队列的共同特点是（ A ）。 A．都是操作受限的线性结构 B．元素都可以随机进出 C．都是先进后出 D．都是先进先出 6. 10,6,2,1按顺序依次进栈，该队列的可能输出序列是（ A ）。 . (进栈出栈可以交替进行）。 A．6,10,1,2 B．2,10,6,1 C．6,1,10,1 D．1,6,10,2 7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ B ）。 A. f->next=p; f=p; B． r->next=p;r=p; C． r=p; p->next=r; D． p->next=f;f=p; 8. 对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 ( B ）。 A．e= top->next; top->data=e; B．e=top->data; top=top->next; C．top=top->next; e=top->data; D．top=top->next; e=data; 9. 数据结构中，与所使用的计算机无关的是数据的( A ) 结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 10. 算法的时间复杂度与( A )有关。 A. 算法本身 B. 所使用的计算机 C. 算法的程序设计 D. 数据结构 11．顺序表所具备的特点之一是（ A ）。 A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素 12．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行 s->next=p->next; 和（ D ）。 . A．p= s; B． p->next=s->next; C．p=s->next D． p->next=s; 13. 数据元素是数据的基本单位，它（ C ）。 A．只能有一个数据项组成 B．至少有二个数据项组成 C．可以是一个数据项也可以由若干个数据项组成 D．至少有一个数据项为指针类型 14. 一种逻辑结构在存储时 （ C）。 A．只要存储数据元素间的关系 B．只能采用一种存储结构 C．可采用不同的存储结构 D．只要存储数据元素的值 15．设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（C ）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 16.单向链表所具备的特点是( C )。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点

17. 在线性表的顺序结构中，以下说法正确的是（C ）。 A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的 C．逻辑上相邻的元素在物理位置上也相邻 D．进行数据元素的插入、删除效率较高 18.数据结构在计算机内存中的表示是指 ( B ) 。 . A．数据元素之间的关系 B．数据的存储结构 C．数据元素的类型 D．数据的逻辑结构 19.对链表, 以下叙述中正确的是（ A ）。 A．不能随机访问任一结点 B．结点占用的存储空间是连续的 C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 20.下面关于线性表的叙述中,错误的是( B )。 A . 线性表采用顺序存储,必须占用一片连续的存储空间。 B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。 C. 线性表采用链式存储，不必占用连续的存储空间。 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（B ）。 A．30 B．31 C. 5 D．6 22 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B ）。 A．15 B．14 C. 5 D．6 23．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 A．11 B．10 C．30 D．31 24．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 . A．10 B．17 C．15 D．16 25．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ C ）。 A．25 B．24 C．26 D．27 26．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ D ）。 A．62, B．63 C．51 D．53 27．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问 该结点的前驱结点，则采用（A ）的存储方式是不可行的。 A．单向链表 B．双向链表 C．单向循环链表 D．顺序表 28．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行snext=rearnext ;和（ D ）。 A． rearnext= snext; B． rear =snext; C． rear=s; D． rearnext=s; 29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ B ）。 A．i/2.0 B．2*i C．2*i+1 D．i+2 30．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D ）。 A．30 B．8 C．31 D．7 二、填空题 . 1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是___ 6_____。 2. 结构中的元素之间存在一对多的关系是___树形_____结构。 3. 数据结构中，数据元素之间的抽象关系称为____逻辑____结构。 4. 结构中的元素之间存在多对多的关系是 ___图状_____结构 。 5. 栈的操作特点是后进___先出_____ 。 6. 循环队列的最大存储空间为MaxSize ,若队头指针front，队尾指针rear，采用少用一个 存储空间以有效地判断栈空或栈满，队空的判定条件为___ rear==front为真_____ 。 7. 广义表(( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是____（b,a,c）____。 8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是____ 6____。 9. 设有一个长度为18的顺序表 , 第8号元素到第18号元素依次存放的值为8,9,…,18. 某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i]; 即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这 样做是错误的.其结果新表中第9号元素的值为___ 18 _____。 10．要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂 度为____ O(n)___ 。 11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _ 5______个结点。 12．一棵有8个叶结点的二叉树，其1度结点的个数为3，则该树共有 ___ 18____个结点。 13．设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有 6 个结点。 （根所在结点为第1层） 14.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有__ n+1______个指针域为空。 . 15．中序遍历____二叉排序树 ____树可得到一个有序序列。 16. 对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较__ 4______次。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是____ 10，12，11，13，14，16____。 （按升序排序） 18．设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有__ 34_____个结点。（根所在结点为第1层） 19. 对16个元素的序列用冒泡排序法进行排序，共需要进行___ 15_____趟冒泡。 20．一棵有16个叶结点的哈夫曼树，则该树共有___ 31____个结点。 21. 一棵有16个叶结点的哈夫曼树，则该树共有__ 15_____个非叶结点。 22. 20个元素进行冒泡法排序，通常第6趟冒泡要进行__ _ 14___次元素间的比较。 23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排 序) ，当把第7个记录46插入到有序表时，为寻找插入位置需比较____3____次。 24．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个零 元素，其相应的三元组表共有____4___个元素。

三、综合题 1． 设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序号依次为 1,2,3,……，11.

合集下载

《数据结构》期末考试复习题及参考答案

《数据结构》期末考试复习题及参考答案

数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。

2.___栈__又称为LIFO表。

3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。

4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。

5.在串S=“structure”中，以r为首字符的子串有_9_个。

6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。

7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。

8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。

9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。

10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。

11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。

12.一棵深度为5的满二叉树中的结点数为_______31_______个。

13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。

14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。

15._____拓朴排序______可以判断出一个有向图中是否有环。

数据结构期末试题及答案

数据结构期末试题及答案

数据结构期末试题及答案一、选择题（每题2分，共20分）1. 下列哪一项不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个直接前驱和一个直接后继C. 有多个根节点D. 有且只有一个叶子节点2. 在顺序存储结构中，数据元素之间的逻辑关系由（）表示。

A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置3. 在链式存储结构中，数据元素之间的逻辑关系由（）表示。

A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置4. 下列哪种排序算法的平均时间复杂度是O(nlogn)？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序5. 下列哪种数据结构属于非线性结构？A. 栈B. 队列C. 线性表D. 树二、填空题（每题2分，共20分）6. 一个栈的初始状态为空。

首先将元素1、2、3、4、5依次进栈，然后退栈一次，再让元素6、7依次进栈，此时栈顶元素的值为______。

7. 一个队列的初始状态为空。

首先将元素a、b、c、d、e依次入队，然后出队两次，再让元素f、g依次入队，此时队列的头部元素为______。

8. 在二分查找法中，每次查找都将查找区间分为______两部分。

9. 在顺序存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。

10. 在链式存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。

三、计算题（每题10分，共30分）11. 给定一个长度为8的数组A[8] = {5, 2, 9, 1, 5, 6, 3, 7}，请写出冒泡排序算法的实现过程，并计算排序后的数组。

12. 请手写一个递归函数，实现计算斐波那契数列的第n 项（n为非负整数）。

13. 请手写一个非递归函数，实现计算斐波那契数列的第n项（n为非负整数）。

数据结构期末试题答案一、选择题答案1. C2. C3. A4. B5. D二、填空题答案6. 77. b8. 相等9. n10. n-1三、计算题答案11. 冒泡排序算法实现过程：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j] A = [5, 2, 9, 1, 5, 6, 3, 7]bubble_sort(A)print(A) 输出排序后的数组```排序后的数组：[1, 2, 3, 5, 5, 6, 7, 9]12. 递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_recursive(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)n = 10 计算斐波那契数列的第10项print(fibonacci_recursive(n)) 输出结果```13. 非递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_iterative(n):a, b = 0, 1for _ in range(n):a, b = b, a + breturn an = 10 计算斐波那契数列的第10项print(fibonacci_iterative(n)) 输出结果```以上为数据结构期末试题及答案，希望对您有所帮助。

国家开放大学最新《数据结构(本)》期末综合练习(填空题)测验答案解析

国家开放大学最新《数据结构(本)》期末综合练习(填空题)测验答案解析

国家开放大学最新《数据结构（本）》期末综合练习（填空题）测验答案解析试题1满分1.00未标记标记试题试题正文对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。

该矩阵A有回答列。

反馈正确答案是：10试题2满分1.00未标记标记试题试题正文结构中的数据元素存在多对多的关系称为回答结构。

反馈正确答案是：图状试题3满分1.00未标记标记试题试题正文在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作回答= q->next;。

反馈正确答案是：p->next;试题4满分1.00未标记标记试题试题正文n个元素进行冒泡法排序，第j趟冒泡要进行回答次元素间的比较。

反馈正确答案是：n-j试题5满分1.00未标记标记试题试题正文对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和回答三项信息。

反馈正确答案是：数组元素试题6未标记标记试题试题正文中序遍历回答树可得到一个有序序列。

反馈正确答案是：二叉排序树试题7满分1.00未标记标记试题试题正文队列的操作特点是后进回答。

反馈正确答案是：后出试题8满分1.00未标记标记试题试题正文待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为回答。

反馈正确答案是：1，2，4，8，3，5，9满分1.00未标记标记试题试题正文n个元素进行冒泡法排序，通常需要进行回答趟冒泡。

反馈正确答案是：n-1试题10满分1.00未标记标记试题试题正文广义表（（a，b），d，e（（i，j），k））的长度是回答。

反馈正确答案是：4试题11满分1.00未标记标记试题试题正文中序遍历二叉排序树可得到一个回答的序列。

反馈正确答案是：有序试题12满分1.00未标记标记试题试题正文广义表的（c，a，（a，b），d，e，（（i，j），k））深度是回答。

北京理工大学2014-2015学年数据结构期末考试卷

北京理工大学2014-2015学年数据结构期末考试卷

北京理工大学2014-2015学年数据结构期末考试卷北京理工大学2014-2015学年第一学期《数据结构》期末考试试题（A）一、选择题（24分）1，下面关于线性表的叙述错误的是（）。

（A）线性表采用顺序存储必须占用一片连续的存储空间（B）线性表采用链式存储不必占用一片连续的存储空间（C）线性表采用链式存储便于插入和删除操作的实现（D）线性表采用顺序存储便于插入和删除操作的实现2，设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

（A）2m-1（B）2m（C）2m+1（D）4m3，设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）（A）R-F（B）F-R（C）（R-F+M）%M（D）（F-R+M）%M4，设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

（A）BADC（B）BCDA（C）CDAB（D）CBDA5，设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

（A）n（n-1）/2（B）n（n-1）（C）n2（D）n2-1，6，设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）（А）9（B）10（C）11（D）127，设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

（A）n-1（B）n（C）n+1（D）2n-18，设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

（A）2，3，5，8，6（B）3，2，5，8，6（C）3，2，5，6，8（D）2，3，6，5，8二、填空题（24 分）1，为了能有效地应用HASH查找技术，必须解决的两个问题是________________和________________________。