《数据结构》模拟卷(B卷)

《《数据结构》模拟卷(B卷)》由会员分享，可在线阅读，更多相关《《数据结构》模拟卷(B卷)（9页珍藏版）》请在装配图网上搜索。

1、数据结构模拟卷、单项选择题1.以下与数据的存储结构无关的术语是（C )。2.3.4.A.循环队列B. 链表以下数据结构中，哪一个是线性结构（A.广义表B.二叉树 C.C.哈希表D )。稀疏矩阵D.D.以下那一个术语与数据的存储结构无关？（B. 哈希表 C.线索树D.双向链表在下面的程序段中，对 x的赋值语句的频度为（FOR i:=1 TOn DOFOR j:=1 TO nDOx:=x+1;A. O(2 n)B.O(n)2C. O(n).O(log 2n)5. 下面关于线性表的叙述中，错误的是哪一个（ BA. 线性表采用顺序存储，必须占用一片连续的存储单元。B. 线性表采用顺序存储，便于进行插入

2、和删除操作。C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。6. 线性表是具有 门个（C ）的有限序列（n0）A.表元素 B .字符C.数据元素D .数据项 E .信息项7. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。A.顺序表B .双链表 C .带头结点的双循环链表D .单循环链表8. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A .单链表B .仅有头指针的单循环链表C .双链表D.仅有尾指针的单循环链表9.

3、下面给出的四种排序法中（D ）排序法是不稳定性排序法。A.插入 B.冒泡C.路归并D.堆积10. 下列排序算法中，其中( D )是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序11.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为A. -A+B*C/DEB. -A+B*CD/E C-+*ABC/DED. -+A*BC/DE12.算术表达式a+b* (c+d/e )转为后缀表达式后为(B )。A. ab+cde/*B. abcde/+*+C . abcde/*+ D . abcde*/+二、填空题，在横线

4、处填写合适内容1. 数据结构的存储结构包括顺序、链式、索引和散列等四种。2. 在程序运行过程中可以扩充的数组是 动态存储分配的数组。这种数组在声明它时需要使用数组指针。3. 在链表中进行插入和_删除操作的效率比在顺序存储结构中进行相同操作的效率高。4. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为后进先出_表。5. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是递归的对象。6. 一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点f的层数为3假定树根结点的层数为0。7. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯

5、定没有 根 子女。8. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根 结点的左子树 上。，从顶点1出发，对图G9. 设图 G=(V,E) , V=1,2,3,4, E=,进行广度优先搜索的序列有2种。10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做 交换 排序。11快速排序在平均情况下的空间复杂度为 O（nlogn） 。12.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为_500_。三、判断题1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，

6、则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则 得到的是最优二叉搜索树（错 ）3. 对于AOE网络，加速任一关键活动都能使整个工程提前完成（对）4. 直接选择排序是一种稳定的排序方法（错）5. 闭散列法通常比开散列法时间效率更高（错）6. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对）7. 顺序表和一维数组一样，都可以按下标随机（或直接）访问（对）8. 在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置（错）9. 用非递归方法实现递归算法时一定要使用递

7、归工作栈（对）10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对）四、运算题1. 设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存储地址是200,每个数组元素占1个存储字，则A62的存储字地址是多少。A 62的存储字地址：3442. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1 ）和度为2、度为1及度为0的结点个数。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a求解一下问题:高度：度为1的结点数：3度为2的结点数：3度为0的结点数

8、：43. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转” 、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？左单旋转结点个数：1右单旋转结点个数：0先左后右双旋转结点个数：1先右后左双旋转结点个数：0不调整结点个数：64. 已知一个带权图的顶点集V和边集G分别为：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)1

9、2;试根据迪克斯特拉(Dijkstra) 算法求出从顶点0到其余各顶点的最短路径，在下面填写5.已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划分后对应的路径长度。顶点：01 23 45 6路径长度：0161014252131数据表的变化。(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 5325* 25 36 53 40 6225*25 36 40 53 62五、算法设计题1设有一个表头为first 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点按逆序链接。template vclass Type vo

10、id List : Tn erse() if (first= NULL )return ;ListNode * p=first 宀 link ; , *pr =NULL ; While (p 匸NULL ) First link =pr ;Pr =first ;first =p ;p =p link;first -li nk =pr ;When you are old and grey and full of sleep,And no ddi ng by the fire, take down this book,And slowly read, and dream of the soft l

11、ookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love

12、 fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you dont know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you cant se

13、e my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I pla inly cannot resist the year ningYet prete nding you have n ever bee n in my heart.The furthest dista nee in the worldIs not strugg

14、li ng aga inst the tidesBut using on es in differe nt heartTo dig an un crossable riverFor the one who loves you.Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How m

15、any loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his

16、face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you dont know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you cant see my loveBut whe n un doubtedly knowing the love from

17、bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I pla inly cannot resist the year ningYet prete nding you have n ever bee n in my heart.The furthest dista nee in the worldIs not struggli ng aga inst the tidesBut using on es in differe nt heartTo dig an un crossable riverFor the one who loves you.