数据结构考试题

一、单项选择

1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的

①q、数据信息在计算机中的

②A以及一组相关的运算等的课程

①A.操作对象B.计算方法C.逻辑结构D.数据映象

②A.存储结构B.关系C.运算D.算法

2.以下数据结构中，D是线性结构A.广义表B.二叉树C.稀疏矩阵D.串

3.从逻辑上可以把数据结构分为C两大类A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和构造型结构

4.以下数据结构中，D是线性结构A.广义表B.二叉树C.稀疏矩阵D.串

5.以下数据结构中，D是非线性结构A.栈B.二叉树C.队列D.字符串数据结构DSData Slrucl可以被形式地定义为DS=D,R,其中D是

①B的有限集合,R是D上的

②D有限集合

①A.算法B.数据元素C.数据操作D.数据对象

②A.操作B.映象C.存储D.关系

6.线性表的顺序存储结构是一种

①上—的存储结构，线性表的链式存储结构是一种的

②B存储结构A.随机存取B.顺序存取C.索引存取D.散列存取

42.已知一个图用领接矩阵表示，计算第i个结点的入度的方法是一求第i列非零元素的和.

43.G是一个非连通的无向图，共有28条边，则该图至少有9个顶点.

44.一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的-010-

45.从邻接矩阵4=I01可以看出，该图共有3个顶点.如果是无向图，则共有条边.

01046.n个顶点的连通图用邻接矩阵表示时，则该矩阵至少有2n-l个顶点.

47.设图中有n个顶点，e条边，如果用邻接表表示图，进行深度优先搜索遍历的时间复杂度为On+e,如果用邻接矩阵表示图，时间复杂度为OS

48.从平均时间性能而言，快速排序排序最佳.

三、堆排序是一.选.排序.堆实质上.一棵完全二叉.结点的层次序列.对于含有n个元素的排序.堆排序的时间复杂度...所需附加的存储结点.

01..

四、用图表回答下列问题设某通信系统使用出现的频率w={5,29,7,8,14,23,3,11,试构造对应的哈夫曼树请按左子树根结点的权小于右子树树根结点的权的次序构造？答案如图根据下面的邻接链表，画出相应的图，写出每个顶点的度，并用邻接矩阵表示.答案如图所Vl:3V2:2V3:3V4:2V5:4V6:20000000000先根遍历序列ABDEGFC答案如图所示10000001000011010000画出和下列二叉树对应的森林:答:

1.阅读下列算法，按要求做答.

2.下面是删除单链表L中最大元素所在结点的类C语言算法，请补足缺失部分使其完整.void DelMaxLinkListL{r=L;p=L-next;ifPm=p-data;1;p=p-next;whilep{iff2{3;m=p-data;}4;p=p-next;q=r-next;⑸；freeq;答案1L-next=NULL;2p!=NULL;3q!=NULL;4p-next=r-next5r-next=p.阅读下列算法，说明该算法的作用Status algorithm1LinkQueue Q{SqStack Stack;QEIemType Element;InitStackStack;while!QueueEmpty Q{DeQueueQ,Element;PushStack,Element;wh ile!StackEmptyStack{PopStack,Element;EnQueueQ,Element;答利用栈实现队列的逆置.阅读下列算法，说明该算法的作用Status algorithm2Stack S,int e{Stack T;int d;InitStackT;while!StackEmptyS{PopS,d;ifd!=e PushT,d；while!StackEmpty T{PopT,d;PushS,d;答利用辅助栈T,将栈S中的元素e删除.

3.将下面程序改写成递归过程.void algorithm3int n{int i=n;whileil{printfi—;答void algorithm4int j{printfj；algorithm4j-l阅读下列算法，说明该算法的作用BiTree algorithmsElemTypePrefl,ElemType In[]{int PreLen,InLen;int i,j;BiTree BT;ElemType*subPre,*subln;PreLen=strlenPre;InLen=strlenIn;if PreLen!=InLen||PreLen==0return NULL;for i=0;iInLenIn[i]!=Pre

[0];i++;if i==InLen returnNULL;BT=BiTNode*mallocsizeofBiTNode;BT-data=Pre[0|;subPre=ElemType*malloci+1*sizeofEIemType;subin=ElemType*malloci+1*sizeofElernType;forj=0;ji;j++{subPre[j]=Pre[j+1];subln[j]=In[j];subPrefj]=W;subln[j]=W;BT-lchild=CreatBTsubPre,subin;subPre=ElemType*mallocPreLen-i*sizeofElemType;subin=ElemType*mallocPreLen-i*sizeofElemType;forj=i+l；jPreLen;j+4-{subPre[j-i-l]=Pre|j];subln[j-i-l]=In[j];subPreg-i-1]廿\0;subln[j-i-lj=\0;BT-rchild=CreatBTsubPre,subin;return BT;答利用一棵二又树的先序遍历和中序遍历还原该二叉树.

五、算法设计题设顺序表L中的数据元素递增有序.试写一个算法.将e插入顺序表中.要求插入后保持该表的有序性.void InsertElemSqListL,ElemType{j=L.length-1;whileL.elem[j]e{L.elem[j+l]=L.elem[j];j++L.elem[j+l]=e;L.length++;

1.已知la是带头结点的单链表的头指针，试编写一个逆序输出表中各个元素的递归算法.void TraverseLinkLinkListp{ifp-next TraverseLinkp-next;printfp-data;写一算法，统计二叉树的结点的总个数〃利用中序遍历方法，或者先序、后序均可以void LeafBiTree T,int m{ifT!=NULL{LeafT-lchild,m;〃中根遍历左子树m++;〃计算结点LeafT-rchild,m;〃中根遍历右子树写一算法，求二叉树的高度int heightBiTreeT{if T==NULL return0;else{int hl=heightT-lchild;int hr=heightT-rchild;return1+hlhrhl:hr;//I加上hl和hr的较大值线性表的逻辑顺序与存储顺序总是一致的，这种说法_B_oA.正.......B.不正确

7.下面那一条是顺序存储结构的优点？A..存储密度...B.插入运算方..C.删除运算方.D.可以方便的用于各种逻辑结构的存储表示

8.线性表采用链式存储结构时，要求内存中可用的存储单元的地址...必须是连续…B.部分地址必须是连续..C.一定不连续D.连续和不连续都可以

9.表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需要移动元素的平均次数为E,删除一个元素所需要移动元素的平均次数为AA.n-l/..B...C.n+..D.n-..E.n/..F.n+l/.G.n-2/

11.在一个单链表中，若删除p所指向结点的后继结点，则执行_A.p-next.p-next-nex...B.p=p-next.p-next.p-next-nextC.p.p-next-nex.......D.p.p-next若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,•••»pn,若pl=n,则pi为_C...A..…B.n=...C.n-i+...D.不确定写一算法，交换二叉树的左右子树BiTNode Permute_childBiTNode*T{BiTNode*temp;ifT{Permute_childT-lchild;Permute_childT-rchild;temp=T-lchild;T-lchild=BT-rchild;T-rchild=temp;

2.已知二叉树采用二叉链表存储，设计算法，判定两棵二叉树是否相似Statues likeBiTreeS,BiTreeT{ifT二二NULLS==NULL return1;else ifSTreturn likeS-lchild,T-lchildlikeS-rchild,T-rchild;else return0;

12.设栈的输入次序为1,2,3,4,5,则不可能是其出栈序列，...A.

5432..B.

4532..C.

4351...D.

1234513.一个递归算法必须包括BA.递归部.…B.终止条件和递归部分C.迭代部.…D.终止条件和迭代部分

14.用链接方式存储的队列，在进行删除操作时D.仅修改头指.…B.仅修改尾指针C.头尾指针都要修..D.头尾指针可能都要修改

15.数组A[m]存放循环队列的元素，其头尾指针分别是front和rear,则当前队列的元素个数是A A.rear-front+m%.B.front-rear+m%,C.front-rear+.D.rear-front+

17.从一个栈顶指针HS的链表中删除一个结点，用x保存被删除的结点值，执行的语句为_C_A.x=HS.HS=HS-nex.......B.HS=HS-next.x=HS-dataC.x=HS-data.HS=HS-nex....D.HS-next=HS.x=HS-data

19.下面关于串的叙述，哪一个是不正确的_B_A.串是字符的有限序……B.空串是由空格构成的串C.匹配模式是串的一种重要运..D.串可以采用链式存储结构设有两个串p和q,求q在p中首次出现的位置的运算称作_B_A.连.......B.模式匹配C.求子......D.求串长

20.若串s=software,其子串的数目为BA....B.

3...C.

3...D.9二维数组A中，每个元素A的长度为3个字节，行下标i从到7,列下标j从到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A

[7]

[4]的起始地址为_C_A.SA+

14..B.SA+

14...C.SA+22…D.SA+

22521.对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运.…B.便于输入输出.节省存储空……D.降低运算的时间复杂度

22.在以下叙述中正确的是」A.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出

23.广义表Xa.a的表头为C,表尾为C.A.….B....C.a...D.a

24.己知广义表L=x,y,z,a,u,t,w,从L中取出原子项t的运算为—D—A.HeadTailTailL....B.TailHeadHeadTailLC.HeadTailHeadTailL.D.HeadTailHeadTailTailL

25.树最适合用来表示BA.有序的数据元.….B.数据之间具有分支层次关系的数据C.无序的数据元..…D.无太多关系的数据元素如果某二叉树的前根次序遍历结果为sluwv,中序遍历为uwtvs,那么该二叉树的后序为_B_A.uwvt....B.vwut....C.wuvt...D.wutsv某二叉树的前序遍历结点访问顺序是abdgceih,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_D A.bdgcefh...B.gdbecfh...C.bdgaech...D.gdbehfca在一非空二叉树的中序遍历序列中，根结点的右边_A_A.只有右子树上的所有结…B.只有右子树上的部分结点C.只有左子树上的部分结…D.只有左子树上的所有结点设和n是一棵二叉树上的两个结点，在中序遍历,n在m前的条件是上的右...B.n是m的祖先在的左…D.n是m的子孙在

27.深度为5的二叉树至多有_C__个结点

28.由权8,2,5,7的四个叶子结点构造棵哈夫曼树，该树的带权路径长度为工A.

2...B.

3...C.

4...D.43A.l...B.

3...C.

3...D.

1029.利用二叉链表存储树，则根结点的右指针是CA.指向最左孩…B.指向最右孩…C....D.非空

30.下列存储方式中，哪一个不是树的存储形式？DA.双亲表示….B.孩子链表表示..C.孩子兄弟表示…D.顺序存储表示法在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍A.1/•・・・・・・♦・・C・•・・・D••

31.具有n个顶点和多于n-1条边的无向图B.A.有可能是..B.一定不是..C.一定是..D.以上答案都不对

32.具有6个顶点的无向图至少应有_A_条边才能确保是一个连通图

33.无向图G=V,E,其中:V={a,b,c,d,e,f},E={a,b,a,e,a,c,b,e,c,f,f,d,e,d},则对该图进行深度优先遍历,得到的序列为:26A.C knnmmmA.abecd...B.acfeb...C.aebcf...D.aedfcb下述几种排序方法中，要求内存量最大的是_D_A.插入排..B.选择排…C.快速排・.D.归并排序排序方法中，从未排序序列中依次取出元素与己排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法,称为_C_OA.希尔排..B.起泡排..C.插入排..D.选择排序A.在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_插入排..B.选择排..C.快速排..D.归并排序

34.下列排序算法中，哪一个是稳定的排序算法？BA.直接选择排..B.二分法插入排..C.希尔排..D.快速排序

35.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数AA.......B.2n-…C.2…D.n-1

二、填空题

1.算法的五个重要特性是一有穷性,确定性，可行性,输入和输出.

2.数据的树型结构和图（网）状结构合称非线性结构.

3.抽象数据类型的定义仅取决于它的一组逻辑特性，而与数据在计算机中的表示和实现无关.

4.评价算法质量的指标是正确性，易读性，健壮性，高效性.

5.数据结构中评价算法的两个重要指标是；时间复杂度和空间复杂度.分析下面算法程序段，的时间复杂度是_Omn_os=0;for i=0;in;i++for j=0;jm;j++s+=B[i]g];

6.当线性表元素的总数基本稳定，且很少进行删除和插入操作时.，但是要求以最快的速度存取线性表中的元素，应该采取顺序存储结构.

7.顺序表中逻辑上相邻的元素的物理位置一必定相邻.而单链表中逻辑上相邻的元素的物理位置上正相邻.

8.在各个结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问n/2个结点.

9.在单链表中设置头指针的作用是简化操作，减少边界条件的判断.

10.在单链表中，除首元结点外，任一结点的存储位置由其直接前驱的指针域指示.

11.对于一个具有n个结点的单链表.在已知p所指向结点后插入一个新结点的时间复杂度.

01..在值域为给定值的结点后插入一个新结点的时间复杂度为0n.

12.在双链表中，每个结点有两个指针域，一个指向.前驱结点另一个指向—后继结点__

13.根据线性表的链式存储结构中每一结点包含的指针个数，将线性表分成单链表和多重链表.

14.在非空双向链表中，在结点q的前面插入结点p的过程如下，请补充p-prior=q-prior;q-prior-next=p;p-next=q;

15.一般情况下，将递归算法转换成等价的非递归算法应该设置一栈.

16.在解决计算机主机与打印机速度不匹配问题时，通常设置一个打印数据缓冲区，该缓冲区通常是一个队列数据结构.

17.循环队列的引入，目的是为了克服」现象.

18.在栈顶指针为HS的链栈中，判断栈空的条件是一HS二NULL.

19.在具有n个单元的循环队列中，如果不专门设置队满标志，则队满时共n-1有个元素.

20.实现字符串拷贝的函数如下，请补足Void strcpychar*s,char*t{while*s++=*l++!=\0;}

21.空格串是—由一个或多个空格字符组成的串其长度等于一其包含的空格个数

22.空串是不包含任何字符的串，其长度为

0.

23.设s=T AMA STUDENT；其长度为

14.

24.组成备的元装只能是字符.

25.设sl=Good,s2=,s3=bye!,则sl.s2和G连接的结果是Good bye!

26.若广义表中每个元素都是原子时，广义表便成为线性表.

27.广义表的表尾是指除第一个元素外，剩余元素组成的表.

28.广义表A=a,b.c,d的表头为a,bed,表尾为.

29.数组的存储结构采用顺序存储方式.

30.设二维数组a[

0..5,

0..6],其每个字节占5个字节，第一个元素的存储地址为1000,若按列存储，则元素a

15.51存储地址为

1175.

31.高度为k的完全二叉树至少有个叶子结点.

32.若一棵二叉树有50个叶子结点，则该二叉树的总结点数至少是迎

33.有n个叶子结点的哈夫曼树的结点总数为2n-l.

34.根据二叉树的定义，具有三个结点的二叉树有4种.

35.某棵二叉树的中序遍历序列为abedefg,后序遍历序列为bdcafge,则该二叉树的前序遍历序列eacbdgf,该二叉树对应的森林包含2棵二叉树.

36.若二叉树采用二叉链表存储结构，要交换其所有分支结点的左，右子树的位置，利用中序遍历方法最为合适.

37.线索二叉树的左线索指向其前驱，右线索指向其后继.

38.树所对应的二叉树其根结点的右子树一定为空.

39.利用树的孩子兄弟表示法存储，可以将一棵树转化成二叉树.

40.设无向图的顶点个数为n,则该图最多有nn-l/2条边.

41.n个顶点的连通图至少有nJ条边.。