《数据结构本期末综合练习》由会员分享，可在线阅读，更多相关《数据结构本期末综合练习（35页珍藏版）》请在金锄头文库上搜索。
1、数据结构期末综合练习2014年12月期末综合练习一一、单项选择题1 .单向链表所具备的特点是（）。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点2 .头指针为head的带头结点的单向链表为空的判定条件是（）为真。A.head二二NULLB.head-next=NULLC.head-next=NULL;D.head-next!=NULL3 .设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为C.134 .设有一个长度为32 的顺序表，要删除第8个元素需移动元素的个数为
2、（25. 245 .栈和队列的共同特点是A .都是线性结构.元素都可以随机进出C.都是先进后出.都是先进先出6 . 一个栈的进栈序列是2,4, 6,8,10,则栈的不可能输出序列是（）（进栈出栈可以交替进行）oA. 2, 4, 6, 8, 10. 8, 6, 10, 2, 4C. 8, 10, 6, 4, 2. 10, 8, 6, 4, 27 .元素1,3,5,7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是）（进栈出栈可以交替进行）。A.7,5,1,3.7,3,1,5C.5,1,3,7,7,5,3,18 .一个队列的入队序列是a,b,c,d,按该队列的可能输出序列使各元素依次
3、入栈，该栈的可能输出序列是）。（进栈出栈可以交替进行）。 c, a, b, d d, a, b, cA.d,c,b,aC.d,b,a,c9 .在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中，其运算为e二fdata;和（）。next;rnext=r; f next=f;Cf=fnext;D10 .在一个链队中，假设f和r分别为队头和队尾指针，P指向一个已生成的结点，现要为该结点的数据域赋值e,并使结点入队的运算为p-data=e;p-next二NULL;和（）。A.f-next=p;f=p;B.r-next=p;r=p;C.p-nex
4、t=r;r=p;D.p-next=f;f=p;11 设有一个对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素，则该矩阵是（）阶的对称矩阵。A.15B.11C.10D.9ai,i），将其12设有一个24阶的对称矩阵A,采用压缩存储的方式（矩阵的第一个元素为三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第30号元素对应于矩阵中的元素是（）A. aio.s B .&9,213 . F 列是 C 语言中 abcd321ABCDA. 21ABCB.C. abcD14 .字符串al= )oA. alC. a315.
5、字符串al= ).A. alC. a316.程序段chara=while( *!=m. 6D.BEIJING” , a2 =B. a2D. a4BEIJING” , a2 =B. a2D. a4English ”O) n+; p+;B. 8aD . as ,58,2的子串的选项是()abcABCD0321aBEI , a3= BEFANGBEF , a3= BEFANG;char *p=a; intn=0;结果中,n的值是(C. 5D. 717 .一棵有20个结点采用链式存储的二叉树中，共有（个指针域为空。20. 1818 .在一棵二叉树中，若编号为5的结点存在左孩子，则左孩子的顺序编号为（）
6、.10 C . 1119 .设一棵哈夫曼树共有18个叶结点，则该树有（. 12）个非叶结点。2,该树结点中共有2020.设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为个指针域为空。则该树有（）个叶结点。A.21.22C.9.1021如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）.gaebcfd D . gaedfcb22已知如图2所示的一个图,的一种顶点序列为（）若从顶点a出 发，按广度优先搜索法进行遍历，则可能得到图223线性表以（）方式存储，能进行折半查.关键字有序的找。B.关键字有序的顺序.顺序24 在有序表（10,23,32, 36
7、, 53, 66, 68, 76,87, 90, 101, 120)中，用折半查找值 53时，经（）次比较后查找成功。25.有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A.22/8.20/8.23/8D.21/826.有一个长度为11的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A.29/11B.33/11C.26/11D.30/1127.排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。A.折半插入排序B.直接插入
8、排序C.归并排序D.选择排序28.设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（）。A.堆排序B.简单选择排序C.快速排序D.归并排序29.排序方法中，从未排序序列中挑选兀素，并将其依次放入已排序序列（初始为空）的一一端的方法，称为（）排序。A.堆B.冒泡C.选择D.快速30.一组记录的关键字序列为（32,65,42,24,26,80），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A.26,24,32,42,65,80BC.26,24,32,65,42,80D24,26,32,42,65,8026,
9、24,32,80,42,65二、填空题1.广义表(a,(a,b),d,e,(i,j),k)的长度是o2结构中的数据元素存在一对多的关系称为结构。3.广义表的(c,a,(a,b),d,e,(i,j),k)深度是。4栈的操作特点是o5.设顺序队列的类型为typedefstructElemTypedataFMaxSise;intfront,rear;Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定，可用语句sq-datasq-rear=x;。6 .广义表的（a,（a,b）,d,e,（i,j）,k）深度是。7 .序列4,2,5,3,8,6,采用冒泡
10、排序算法，经一趟冒泡后，序列的结果是。（按由小到大顺序）8 .广义表（a,b）,d,e,（i,j）,k）的长度是。9 .在对一组记录（50,34,92,19,11,68,56,41,79）进行直接插入排序（由小到大排序），当把第7个记录56插入到有序表时，为寻找插入位置需比较次。10.设顺序队列的类型为typedefstructElemTypedataMaxSise;intfront,rear;Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量X,按教科书约定，可用语句x=sq-datasq-front;和。11 .数据结构中，可以由一个或多
11、个数据项组成。12 .设顺序队列的类型为typedefstructElemTypedataLMaxSise;intfront,rear;Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定，可用语句sq-datasq-rear=x;禾口。13 .循环队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,采用少用一个元素的模式），判断循环队列为满的条件为为真。14 .序列14,12,15,13,18,16,采用冒泡排序算法，经一趟冒泡后，序列的结果是。（由小到大排序）15 .排序算法中，从尚未排序序列中依次取出元素与已排
12、序序列（初始为空）中的元素依次进行比较，然后将其放入已排序序列的正确位置的方法是o16 .数据结构中，之间的抽象关系称为逻辑结构。17 .对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A共有34个零元素，其相应的三元组表共有个元素。18 .循环队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,），判断循环队列为空的条件为为真。19 .在双向链表中，要删除p所指的结点，可以先用语句（p-prior）-next=p-next;然后再用语句（p_next）prior=。20 .排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比
13、较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是o21 .在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向22 .对稀疏矩阵进行压缩存储，可采用三元组表，矩阵元素cb,4对应的三元组为o23 .把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。24 .在双向链表中，要删除p所指的结点，其中所用的一条语句（p-next）-prior=p-prior;的功能是：使P所指结点的直接后继的左指针指向o三、综合题1 .设数据集合a=l,12,5,8,3,10,7,13,9）（1）依次取a中各数据，构造一棵二叉排序树。（2）说明如何依据此二叉树得到a的有序
14、序列。（3）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（4）给出对该二叉树后序遍历的序列。2 .设数据集合a二62,74,30,15,56,481）依次取a中各数据，构造一棵二叉排序树。2）为了成功查找到48需要进行多少次元素间的比较3）给出对该二叉树后序遍历的序列。3 .设有序表为（2,5,11,12,30,48,58,70,78,79,90）,元素的序号依次为1,2,3,11.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）（2）说明成功查找到元素2需要经过多少次比较？（3） 说明不成功查找元素75需要经过多少次比较？（4） 给出中序遍历该折半查找判定树的序列4.设有序表为（3,9,15,26,38,41,53,74,81,96,97,99）,元素的序号依次为1,2
