数据结构导论练习题.doc

1. 二叉树是非线性数据结构，所以 。.它不能用顺序存储结构存储; .它不能用链式存储结构存储; .顺序存储结构和链式存储结构都能存储; .顺序存储结构和链式存储结构都不能使用 2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：连接 模式匹配 求子串 求串长3. 设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是：BCDEF BCDEFG BCPQRST BCDEFEF4. 有向图中一个顶点的度是该顶点的（）A入度 B. 出度 C. 入度与出度之和 D. （入度+出度）/2在双向5. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比6. 树最适合用来表示( )。 A有序数据元素 B. 无序数据元素 C元素之间具有分支层次关系的数据 D. 元素之间无联系的数据7. 循环队列Sq是满队列的条件是 ( ) 。A. Sq-read=Sq-frontB.（Sq-）read+1）maxsize=Sq-frontC. Sq-read=0D. Sq-front=08. 如果结点A有3个兄弟，而且B是A的双亲，则B的度是( )。 A. 4 B. 5 C. 1 D. 39. 连通分量指的是（）A. 无向图中的极小连通子图 B. 无向图中的极大连通子图C. 有向图中的极小连通子图 D. 有向图中的极大连通子图10.有e条边的无向图，若用邻接表存储，表中有（）个边结点。 A. e B. 2e C. e-1 D. 2(e-1)11. 实现图的非递归深度优先搜索算法需使用的辅助数据结构为（） A. 栈 B. 队列 C. 二叉树 D. 树12. 存储无向图的邻接矩阵一定是一个（） A. 上三角矩阵 B.稀疏矩阵 C. 对称矩阵 D. 对角矩阵13. 在栈顶一端可进行的全部操作是( )。A. 插入 B. 删除 C. 插入和删除 D. 进栈 14. 实现图的广度优先搜索算法需使用的辅助数据结构为（） A 栈 B. 队列 C. 二叉树 D. 树15. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。A p-prior=q;q-next=p； p- prior - next=q； q-prior=q；B p- prior=q； p- prior - next=q ； q- next= p； q- prior=p- prior；C q- next=p； q-prior=p- prior； p- prior - next=q; p- prior=q;D q- prior=p- prior；q- next=p； p- prior=q；1. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。2. 具有n个结点的二叉树，采用二叉链表存储，共有_个空链域。3. _又称作先进先出表。4. 线索二叉树的左线索指向其_，右线索指向其_。5. 向一个长度为n的向量中删除第i个元素(1in)时，需向前移动_ 个元素。6. 用树的孩子兄弟表示法存储，可以将一棵树转换成_。7. 有8个结点的无向图最多有 条边。8. 在作进栈运算时应先判别栈是否_；在作退栈运算时应先判别栈是否_。9. 设有两个串p和q，求q在p中首次出现的位置的运算称作_。10. 二叉树的线索化实质是将二叉链表中的_改为_。11. 无向图中所有顶点的度数之和等于所有边数的_倍。12. 两个串相等的充分必要条件是_。1.写出先序遍历二叉树的递归算法。2.将下列算法填补完整。void LayerOrder(Bitree T)/按层次遍历二叉树InitQueue (Q); /建立工作队列 EnQueue (Q,T);While (!QueueEmpty(Q) DeQueue(Q,p); visit(p);if(p-lchild) EnQueue(Q, _);if(p-rchild) _;/LayerOrder. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。 （）. 进行折半搜索的表必须是顺序存储的有序表。（）. 强连通分量是有向图中的极大强连通子图。（）. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。（）. 线性表若采用链式存储表示, 在删除时不需要移动元素。（）6 赫夫曼树一定是二叉树。 （）7. 队列只能采用链式存储方式.。 （）8. 二路归并排序的核心操作是将两个有序序列归并为一个有序序列。（）9. 在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear，则队空条件为Q-front = Q-rear。（）10. 空串空格串是一样的。 （）1. 试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。2.假设用于通信的电文仅由(a,b,c,d,e,f,g,h)8个字母组成，字母在电文中出现的频率分别为7，19， 2， 6， 32， 3， 21， 10。试为这8个字母设计哈夫曼编码。3. 已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的