计信DS复习题答案.doc

《计信DS复习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计信《数据结构》复习题答案一、选择题1．如果某数据结构的数据元素的集合为S＝{A，B，C，D，E，F，G}，数据元素之间的关系为R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F＞}，则该数据结构是一种()。A．线性结构B．树结构C．图结构D．链表结构2．设有二维数组A[50][60]，其元素长度为1字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为()。A．820B．720C．1210D．14103．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进

2、入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（）个元素。A．3B．4C．5D．64．串是。A）不少于一个字母的序列B）任意个字母的序列C）不少于一个字符的序列D）有限个字符的序列5．A，B，C，D依次入栈，则不可能的出栈序列是。A）A，B，C，DC）D，C，B，AB）A，C，D，BD）D，A，B，C6．栈和队列的共同点是。A）都是先进后出B）都是先进先出C）只允许在端点处插入和删除D）都采用顺序方式存储7．在线索二叉树中，指针t所指结点没有左子树的充要条件是。A）t->lchi

3、ld==NULLB）t->ltag==1C）t->ltag==1且t->lchild==NULLD）t->ltag==08．对具有n个结点的完全二叉树按自上而下、从左至右的顺序，从1开始依次给结点编号，则编号最小的叶子结点的序号是。A）B）+1C）-1D）-19．下列算法中是用来构造无向连通图的最小生成树的。A）FloydB）KruskalC）HuffmanD）Dijkstra10．下列排序算法中是稳定的。A）堆排序B）希尔排序C）快速排序D）归并排序11．若要对一个线性表既能较快地查找，又能适应动态变化的要求，则可采用查找方法。A）分块B）顺

4、序C）折半D）哈希12．下面关于线性表的叙述中，错误的是。A）线性表采用顺序方式存储，必须占用一片连续的存储单元B）线性表采用链式存储，便于进行插入和删除操作C）线性表采用链式存储，不必占用一片连续的存储单元D）线性表采用顺序方式存储，便于进行插入和删除操作13．广义表A=（（a,b,c），（d,e,f）），从A中取出原子e的运算是。A）tail(head(A))B）head(tail(tail(head(A))))C）head(tail(A))D）head(tail(head(tail(A))))14．判定一个指针ST指向的顺序栈（栈中最多元

5、素为M个）为栈满的条件是。A）ST->top!=0B）ST->top==0C）ST->top!=M-1D）ST->top==M-115．指针head指向一个非空循环单链表的头结点，指针p指向该链表的尾结点的条件是。A）p->next=NULLB）p=NULLC）p->next=headD）p=head16．设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为：6，23，3，5和12，按哈夫曼编码（要求左子树根结点的权小于等于右子树根结点的权），则字母C的编码应是。A．10B．110C．1110D．111117．下面关于二叉树

6、的叙述中正确的是。A）二叉树中，任何一个结点的左子树和右子树上的结点个数一样B）二叉树中的结点个数大于0C）二叉树中叶子结点的个数等于度为2的结点个数加1D）二叉树中任何一个结点要么是叶子，要么恰有两个孩子18．具有n个顶点的连通无向图的最小生成树中包含条边。A）nB）n-1C）n+1D）2n19．折半查找存储结构。A）只适用于顺序B）只适用于链式C）既适合于顺序也适合于链式D）既不适合于顺序也不适合于链式20．已知某算法的执行时间为（n3+n2+n）log2(n+2)，n为问题规模，则该算法的时间复杂度是（）。A．O(n)B．O(n2)C．O

7、(log2n)D．O(n3log2n)1234567891011121314151617181920BCADDCBBBDADDDCCCBAD二、判断题1．算法与程序没有区别，所以在数据结构中两者是通用的。2．串长度是指串中不同字符的个数。3．栈是一种后进先出表。4．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。5．根据线性表的链式存储结构中每个结点所含指针的个数，链表分为单链表和双链表。6．具有3个结点且高度也为3的有序树只有1种形态。7．先序序列和中序序列相同的二叉树是空二叉树或任一结点均无右子树的非空二叉树。8．“AOV网”的

8、中文含义是边表示活动的网。9．在栈满的情况下不能作进栈的运算，否则产生“上溢”。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表