还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
1、单项选择
1.数据结构是一门研究非数值计算的程序设计问题中数据元素的
①C、数据信息在计算机中的
②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.数据结构DSDataStruct可以被形式地定义为DS=(D,R),其中D是
①B的有限集合,R是D上的
②D有限集合
①A.算法B.数据元素C.数据操作D.数据对象
②A.操作B.映象C.存储D.关系
6.线性表的顺序存储结构是一种
①A的存储结构线性表的链式存储结构是一种的
②B存储结构A.随机存取B.顺序存取C.索引存取D.散列存取
7.线性表的逻辑顺序与存储顺序总是一致的,这种说法__B_A.正确B.不正确
8.下面那一条是顺序存储结构的优点AA.存储密度大B.插入运算方便C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示
9.线性表采用链式存储结构时要求内存中可用的存储单元的地址.A.必须是连续的B.部分地址必须是连续的C.一定不连续D.连续和不连续都可以
10.表长为n的顺序存储的线性表当在任何位置上插入和删除一个元素的概率相等时插入一个元素所需要移动元素的平均次数为E删除一个元素所需要移动元素的平均次数为AA.n-1/2B.nC.n+1D.n-1E.n/2F.n+1/2G.n-2/
211.带头结点的单链表head为空的判定条件是_B___A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL
12.在一个单链表中若删除p所指向结点的后继结点则执行_A___A.p-next=p-next-nextB.p=p-next;p-next=p-next-nextC.p=p-next-nextD.p=p-next
13.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为_C___A.iB.n=iC.n-i+1D.不确定
14.设栈的输入次序为:12345则不可能是其出栈序列.A.54321B.45321C.43512D.
1234515.一个递归算法必须包括BA.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分
16.用链接方式存储的队列在进行删除操作时DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改
17.数组A[m]存放循环队列的元素其头尾指针分别是front和rear则当前队列的元素个数是__A__A.rear-front+m%mB.front-rear+m%mC.front-rear+1D.rear-front+
118.栈和队列的共同特点__C__A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点
19.一个栈的入栈序列a,b,c,d,e,则栈的输出序列是__A__A.edcbaB.decbaC.dceabD.abcde
20.栈的特点是__B__,队列的特点是__A__A.先进先出B.先进后出
21.从一个栈顶指针HS的链表中删除一个结点用x保存被删除的结点值执行的语句为__C__A.x=HS;HS=HS-nextB.HS=HS-next;x=HS-dataC.x=HS-data;HS=HS-nextD.HS-next=HS;x=HS-data
22.在链队列Q中插入s所指向的结点执行的语句为__B__A.Q.front-next=s;B.Q.rear-next=s;Q.rear=sC.s-next=Q.rear;Q.rear=sD.s-next=Q.front;Q.front=s
23.空串与空格串是相同的,这种说法__B__A.正确B.不正确
24.下面关于串的叙述哪一个是不正确的__B__A.串是字符的有限序列B.空串是由空格构成的串C.匹配模式是串的一种重要运算D.串可以采用链式存储结构
25.设有两个串p和q,求q在p中首次出现的位置的运算称作__B__A.连接B.模式匹配C.求子串D.求串长
26.若串s=software其子串的数目为BA.8B.37C.36D.
927.二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按行存放时,数组元素A
[7]
[4]的起始地址为__C__A.SA+141B.SA+144C.SA+222D.SA+
22528.对稀疏矩阵进行压缩存储的目的是__C__.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.降低运算的时间复杂度
29.在以下叙述中正确的是BA.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出
30.广义表aa的表头为C表尾为C.A.B.aC.aD.a
31.已知广义表L=xyzautw从L中取出原子项t的运算为__D__A.HeadTailTailLB.TailHeadHeadTailLC.HeadTailHeadTailLD.HeadTailHeadTailTailL
32.树最适合用来表示BA.有序的数据元素B.数据之间具有分支层次关系的数据C.无序的数据元素D.无太多关系的数据元素
33.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为__B__A.uwvtsB.vwutsC.wuvtsD.wutsv
34.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是__D__A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
35.在一非空二叉树的中序遍历序列中,根结点的右边__A__A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点
36.设m和n是一棵二叉树上的两个结点在中序遍历n在m前的条件是CA.n在m的右方B.n是m的祖先C.n在m的左方D.n是m的子孙
37.深度为5的二叉树至多有__C__个结点A.16B.32C.31D.
1038.由权8257的四个叶子结点构造一棵哈夫曼树该树的带权路径长度为DA.23B.37C.46D.
4339.利用二叉链表存储树则根结点的右指针是CA.指向最左孩子B.指向最右孩子C.空D.非空
40.下列存储方式中哪一个不是树的存储形式DA.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法
41.在一个无向图中,所有顶点的度数之和等于所有边数的__C__倍A.1/2B.1C.2D.
442.具有n个顶点和多于n-1条边的无向图B.A.有可能是树B.一定不是树C.一定是树D.以上答案都不对
43.具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图A.5B.6C.7D.
844.无向图G=VE其中:V={abcdef}E={abaeacbecffded}则对该图进行深度优先遍历得到的序列为:DA.abecdfB.acfebdC.aebcfdD.aedfcb
45.下述几种排序方法中,要求内存量最大的是__D__A.插入排序B.选择排序C.快速排序D.归并排序
46.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为__C__A.希尔排序B.起泡排序C.插入排序D.选择排序
47.在待排序的元素序列基本有序的前提下,效率最高的排序方法是__A_A.插入排序B.选择排序C.快速排序D.归并排序
48.下列排序算法中哪一个是稳定的排序算法BA.直接选择排序B.二分法插入排序C.希尔排序D.快速排序
49.将两个各有n个元素的有序表归并成一个有序表其最少的比较次数AA.nB.2n-1C.2nD.n-
12、填空题
1.算法的五个重要特性是有穷性确定性可行性输入和输出.
2.数据的树型结构和图网状结构合称非线性结构.
3.抽象数据类型的定义仅取决于它的一组逻辑特性而与数据在计算机中的表示和实现无关.
4.评价算法质量的指标是正确性易读性健壮性高效性.
5.数据结构中评价算法的两个重要指标是:时间复杂度和空间复杂度.
6.分析下面算法(程序段),的时间复杂度是__Omn__s=0;fori=0;in;i++forj=0;jm;j++s+=B[i][j];
7.当线性表元素的总数基本稳定且很少进行删除和插入操作时但是要求以最快的速度存取线性表中的元素应该采取顺序存储结构.
8.顺序表中逻辑上相邻的元素的物理位置必定相邻而单链表中逻辑上相邻的元素的物理位置不一定相邻.
9.在各个结点查找概率相等的情况下从n个结点的单链表中查找一个结点平均要访问n/2个结点.
10.在单链表中设置头指针的作用是:简化操作减少边界条件的判断.
11.在单链表中除首元结点外任一结点的存储位置由其直接前驱的指针域指示.
12.对于一个具有n个结点的单链表在已知p所指向结点后插入一个新结点的时间复杂度是O1在值域为给定值的结点后插入一个新结点的时间复杂度为On.
13.在双链表中,每个结点有两个指针域,一个指向_前驱结点__,另一个指向__后继结点___
14.根据线性表的链式存储结构中每一结点包含的指针个数将线性表分成单链表和多重链表.
15.在非空双向链表中在结点q的前面插入结点p的过程如下请补充p-prior=q-prior;q-prior-next=p;p-next=q;q-prior=p;
16.一般情况下将递归算法转换成等价的非递归算法应该设置栈.
17.在解决计算机主机与打印机速度不匹配问题时通常设置一个打印数据缓冲区该缓冲区通常是一个队列数据结构.
18.循环队列的引入目的是为了克服假溢出现象.
19.在栈顶指针为HS的链栈中判断栈空的条件是HS=NULL.
20.在具有n个单元的循环队列中如果不专门设置队满标志则队满时共n-1有个元素.
21.实现字符串拷贝的函数如下请补足Voidstrcpychar*schar*t{while*s++=*t++!=\0;}
22.空格串是__由一个或多个空格字符组成的串__,其长度等于_其包含的空格个数
23.空串是不包含任何字符的串其长度为
0.
24.设s=IAMASTUDENT其长度为:
14.
25.组成串的元素只能是:字符.
26.设s1=Goods2=s3=bye!则s1s2和s3连接的结果是Goodbye!
27.若广义表中每个元素都是原子时广义表便成为线性表.
28.广义表的表尾是指除第一个元素外剩余元素组成的表.
29.广义表A=abcd的表头为abcd表尾为.
30.数组的存储结构采用顺序存储方式.
31.设二维数组a[
0..
50..6]其每个字节占5个字节第一个元素的存储地址为1000若按列存储则元素a
[55]存储地址为
1175.
32.高度为k的完全二叉树至少有个叶子结点.
33.若一棵二叉树有50个叶子结点则该二叉树的总结点数至少是
99.
34.有n个叶子结点的哈夫曼树的结点总数为2n-
1.
35.根据二叉树的定义具有三个结点的二叉树有4种.
36.某棵二叉树的中序遍历序列为abcdefg后序遍历序列为bdcafge则该二叉树的前序遍历序列eacbdgf该二叉树对应的森林包含2棵二叉树.
37.若二叉树采用二叉链表存储结构要交换其所有分支结点的左右子树的位置利用中序遍历方法最为合适.
38.线索二叉树的左线索指向其前驱右线索指向其后继.
39.树所对应的二叉树其根结点的右子树一定为空.
40.利用树的孩子兄弟表示法存储可以将一棵树转化成二叉树.
41.设无向图的顶点个数为n则该图最多有nn-1/2条边.
42.n个顶点的连通图至少有n-1条边.
43.已知一个图用领接矩阵表示计算第i个结点的入度的方法是求第i列非零元素的和.
44.G是一个非连通的无向图共有28条边则该图至少有9个顶点.
45.一个图的邻接矩阵表示法是唯一的,而邻接表表示法是不唯一的
46.从邻接矩阵可以看出该图共有3个顶点如果是无向图则共有2条边.
47.n个顶点的连通图用邻接矩阵表示时则该矩阵至少有2n-1个顶点.
48.设图中有n个顶点e条边如果用邻接表表示图进行深度优先搜索遍历的时间复杂度为On+e如果用邻接矩阵表示图时间复杂度为
49.从平均时间性能而言快速排序排序最佳.
50.堆排序是一种选择排序堆实质上是一棵完全二叉树结点的层次序列.对于含有n个元素的排序堆排序的时间复杂度为.所需附加的存储结点是O
1.
3、用图表回答下列问题
1.设某通信系统使用A,B,C,D,E,F,G,H个字符,出现的频率w={5,29,7,8,14,23,3,11},试构造对应的哈夫曼树(请按左子树根结点的权小于右子树树根结点的权的次序构造)答案如图:
2.根据下面的邻接链表,画出相应的图,写出每个顶点的度并用邻接矩阵表示.答案如图所示:V1:3V2:3V3:3V4:2V5:5V6:
23.画出下列树对应的二叉树,并写出其先根遍历序列先根遍历序列ABDEGFC答案如图所示:
4.画出和下列二叉树对应的森林答:
4、阅读下列算法,按要求做答.
1.下面是删除单链表L中最大元素所在结点的类C语言算法请补足缺失部分使其完整.voidDelMaxLinkListL{r=L;p=L-next;ifp{m=p-data;1;p=p-next;whilep{if2{3;m=p-data;}4;p=p-next;}q=r-next;5;freeq;}}答案:1q=p;2mp-data;3r=q;4q=p;5r-next=q-next.
2.阅读下列算法,说明该算法的作用Statusalgorithm1LinkQueueQ{SqStackStack;QElemTypeElement;InitStackStack;while!QueueEmptyQ{DeQueueQElement;PushStackElement;}while!StackEmptyStack{PopStackElement;EnQueueQElement;}}答:利用栈实现队列的逆置.
3.阅读下列算法,说明该算法的作用Statusalgorithm2StackSinte{StackT;intd;InitStackT;while!StackEmptyS{PopSd;ifd!=ePushTd;}while!StackEmptyT{PopTd;PushSd;}}答:利用辅助栈T将栈S中的元素e删除.
4.将下面程序改写成递归过程.voidalgorithm3intn{inti=n;whilei1{printfi--;}}答:voidalgorithm4intj{ifj1{printfj;algorithm4j-1}}
5.阅读下列算法,说明该算法的作用BiTreealgorithm5ElemTypePre[]ElemTypeIn[]{intPreLenInLen;intij;BiTreeBT;ElemType*subPre*subIn;PreLen=strlenPre;InLen=strlenIn;ifPreLen!=InLen||PreLen==0returnNULL;fori=0;iInLenIn[i]!=Pre
[0];i++;ifi==InLenreturnNULL;BT=BiTNode*mallocsizeofBiTNode;BT-data=Pre
[0];subPre=ElemType*malloci+1*sizeofElemType;subIn=ElemType*malloci+1*sizeofElemType;forj=0;ji;j++{subPre[j]=Pre[j+1];subIn[j]=In[j];}subPre[j]=\0;subIn[j]=\0;BT-lchild=CreatBTsubPresubIn;subPre=ElemType*mallocPreLen-i*sizeofElemType;subIn=ElemType*mallocPreLen-i*sizeofElemType;forj=i+1;jPreLen;j++{subPre[j-i-1]=Pre[j];subIn[j-i-1]=In[j];}subPre[j-i-1]=\0;subIn[j-i-1]=\0;BT-rchild=CreatBTsubPresubIn;returnBT;}答:利用一棵二叉树的先序遍历和中序遍历还原该二叉树.
5、算法设计题
1.设顺序表L中的数据元素递增有序.试写一个算法将e插入顺序表中要求插入后保持该表的有序性.voidInsertElemSqListLElemType{j=L.length-1;whileL.elem[j]e{L.elem[j+1]=L.elem[j];j--;}L.elem[j+1]=e;L.length++;}
2.已知la是带头结点的单链表的头指针试编写一个逆序输出表中各个元素的递归算法.voidTraverseLinkLinkListp{ifp-nextTraverseLinkp-next;printfp-data;}
3.写一算法,统计二叉树的结点的总个数//利用中序遍历方法,或者先序、后序均可以voidLeafBiTreeTintm{ifT!=NULL{LeafT-lchildm;//中根遍历左子树m++;//计算结点LeafT-rchildm;//中根遍历右子树}}
4.写一算法,求二叉树的高度intheightBiTreeT{ifT==NULLreturn0;else{inthl=heightT-lchild;inthr=heightT-rchild;return1+hlhrhl:hr;//1加上hl和hr的较大值}}
5.写一算法,交换二叉树的左右子树BiTNodePermute_childBiTNode*T{BiTNode*temp;ifT{Permute_childT-lchild;Permute_childT-rchild;temp=T-lchild;T-lchild=BT-rchild;T-rchild=temp;}}
6.已知二叉树采用二叉链表存储设计算法判定两棵二叉树是否相似.StatueslikeBiTreeSBiTreeT{ifT==NULLS==NULLreturn1;elseifSTreturnlikeS-lchildT-lchildlikeS-rchildT-rchild;elsereturn0;}10042F23H1119A5G38B29E14D8C7152958v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3^^^^v1v2v3v4v5V6BDFCAEGBEGDFCAAAAABBBCCCAAAABBBCCC。