计信DS复习题解析.docVIP

计信《数据结构》复习题答案 一、选择题 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．820 B．720 C．1210 D．1410 3．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（ ）个元素。 A．3 B．4 C．5 D．6 4．串是 。 A）不少于一个字母的序列 B）任意个字母的序列 C）不少于一个字符的序列 D）有限个字符的序列 5．A，B，C，D依次入栈，则不可能的出栈序列是 。 A）A，B，C，D C）D，C，B，A B）A，C，D，B D）D，A，B，C 6．栈和队列的共同点是 。 A）都是先进后出 B）都是先进先出 C）只允许在端点处插入和删除 D）都采用顺序方式存储 7．在线索二叉树中，指针t所指结点没有左子树的充要条件是 。 A）t-lchild==NULL B）t-ltag==1 C）t-ltag==1且t-lchild==NULL D）t-ltag==0 8．对具有n个结点的完全二叉树按自上而下、从左至右的顺序，从1开始依次给结点编号，则编号最小的叶子结点的序号是 。 A） B）+1 C）-1 D）-1 9．下列算法中 是用来构造无向连通图的最小生成树的。 A）Floyd B）Kruskal C）Huffman D）Dijkstra 10．下列排序算法中 是稳定的。 A） B）希尔排序 C）快速排序 D）归并排序 11．若要对一个线性表既能较快地查找，又能适应动态变化的要求，则可采用 查找方法。 A）分块 B）顺序 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指向的顺序栈（栈中最多元素为M个）为栈满的条件是 。 A）ST-top!=0 B）ST-top==0 C）ST-top!=M-1 D）ST-top==M-1 15．指针head指向一个非空循环单链表的头结点，指针p指向该链表的尾结点的条件是 。 A）p-next=NULL B）p=NULL C）p-next=head D）p=head 16．设电文中出现的字母为 A 、 B 、 C 、 D 和 E ，每个字母在电文中出现的次数分别为： 6，23，3，5 和 12，按哈夫曼编码（要求左子树根结点的权小于等于右子树根结点的权），则字母 C 的编码应是 。 A．10 B．110 C．1110 D．1111 17．下面关于二叉树的叙述中正确的是 。 A） B）二叉树中的结点个数大于0 C）二叉树中叶子结点的个数等于度为2的结点个数加1 D）二叉树中任何一个结点要么是叶子，要么恰有两个孩子 18．具有n个顶点的连通无向图的最小生成树中包含 条边。 A）