数据结构与算法--课件模拟试卷B.doc

浙江大学远程教育学院试题卷B卷课程名称 数据结构与算法 教学站 年级专业(层次) 学号 姓名 注意：所有试题答案均按题目编号写在答题卷上。一. 单项选择题（每项选择1.5分，共60分） 1、数据结构形式地定义为（D，S），其中D是 的有限集合，S是D上的 的有限集合。 A.算法 B.数据元素 C.逻辑结构 D.数据操作 A.结构 B.操作 C.存储 D.关系2、计算机算法是指 ，它必须具备输入、输出和 等五个特性。 A.计算方法 B.排序方法 C.调度方法 D.解决问题的有限运算序列 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、稳定性和有穷性 D.易读性、稳定性和安全性3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。 A.必须是连续的 B.部分地址必须是连续的 C.连续或者不连续都可以 D.一定是不连续的4、线性表的逻辑顺序和存储顺序总是一致的，这种说法 。 A. 不正确 B.正确5、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是 。 A. edcba B. decba C. dceab D. abcde6、判断一个循环队列Q(最多元素为MAXQSIZE)为空队列的条件是 ，为满队列的条件是 。 A. Q.front = Q.rear B. Q.front != Q.rear C. Q.front = (Q.rear+1)%MAXQSIZE D. Q.rear = (Q.front+1)%MAXQSIZE7、一个一维数组第一个存储单元的地址是100，每个元素的长度是4，则它的第5个元素的地址是 。 A. 120 B. 116 C. 110 D. 104 8、某语言采用低下标优先方式存放数组元素，数组下标从1开始。设维数为（5,6,7）的数组A5x6x7的起始存储地址为Loc111=1000，每个数组元素占用4个字节。则元素A345所在的地址Loc345= 。A.1692 B.1636 C.1436 D.1173 E.1159 F.1109 9、设有三对角矩阵（aij）nxn（1= i,j=n），将其三条对角线上的元素存于数组B3n中，使得：Buv = aij（0= u=2, 0=vnext=NULL C.L!=NULL D.L-next=L 11、在一个单链表L中，已知q所指结点是p所指结点的前驱结点，若要在q和p结点之间插入s结点，则执行 。 A. s-next = p-next; p-next = s; B. p-next = s-next; s-next = p; C. q-next = s; s-next = p; D. p-next = s; s-next = q;12、假设双向链表结点的类型如下：typedef struct DlinkNode int data; /* 数据域 */ struct DlinkNode *prior; /* 指向前驱结点的指针域 */ struct DlinkNode *next; /* 指向后继结点的指针域 */bnode;在一个双向循环链表的p所指结点后插入s结点，则执行 。 A. p-next = s; s-prior = p; p-next-prior = s; s-next = p-next; B. p-next = s; p-next-prior = s; s-prior = p; s-next = p-next; C. s-prior = p; s-next = p-next; p-next = s; p-next-prior = s; D. s-prior = p; s-next = p-next; p-next-prior = s; p-next = s;13、设有两个串p和q，求q在p中首次出现的位置的运算称为 。 A.连接 B.模式匹配 C.求子串 D.求串长14、设串s1 = “ABCDEFG”,s2=”PQRST”，函数Concat(x,y)返回x和y的连接串，Subs(s,i,j)返回串s的从序号i的字母开始的j个字符组成的子串，Length(s)返回串s的长度，则下面函数Concat(Subs(s1,2,Length(s2),Subs(s2,Length(s2),2)的结果串是 。 A. BCDEF B. BCDEFT D. BCPQRST D. BCDEFEF15、设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 。 A. 2h-1 B. 2h D. 2h+1 D. h16、如果某二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca17、树最适合用来表示 。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据18、具有五层结点的平衡二叉树至少有 个结点。 A. 10 B. 12 C. 15 D. 1719、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中， 是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对20、线索二叉树是一种 结构。 A. 逻辑 B. 逻辑和存储 C. 线性 D. 物理21、下图所示的二叉树中， 不是完全二叉树。22、常对数组元素进行的两种基本操作是 。 A. 建立与删除 B. 索引与修改 C. 查找与删除 D. 查找与修改 23、在一个无向图中，所有顶点的度数之和等于所有边数的 倍。 A. 1/2 B. 1 C. 2 D. 4 24、具有4个顶点的无向完全图有 条边。 A. 6 B. 12 C. 16 D. 2025、对于一个具有n个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为 ；邻接表中所有结点总数是 。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. 2e C. e D. n+e26、关于有向图的邻接表和逆邻接表表示法，下列结论 比较正确。 A. 用邻接表表示法计算入度比较方便 B. 用邻接表表示法计算入度和出度都方便 C. 用逆邻接表表示法计算入度和出度都不方便 D. 用逆邻接表表示法计算入度比计算出度方便 27、已知一个图如下图所示，从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为 ；按广度优先搜索法进行遍历，则可能得到的一种顶点序列为 。 A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b28、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。 A. n B. (n+1)/2 C. n/2 D. (n-1)/2 29、在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A. 插入排序 B. 快速排序 C. 归并排序 D. 选择排序 30、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。 A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序31、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为 。 A. 38，40，46，56，79，84 B. 38，46，56，79，40，84 C. 38，40，56，79，46，84 D. 46，38，56，79，40，84 32、快速排序方法在 情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据在含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数33、堆栈和队列的共同点是 。 A. 只允许在端点处插入和删除 B. 都是先进先出 C. 都是先进后出 D. 没有共同点34、一棵二叉树是下列四种树之一，且只有度为0和度为2的结点，那么它是 。 A. 完全二叉树 B. 二叉排序树 C. 堆 D. 最优树二. 填空题（将正确的答案填在相应的空位中,每空1-2分，共20分） 1、设m 和n 为正整数，下面程序段中前置以记号的语句的频度是 。 for (i=0; in; i+) for (j=i; jm; j+) aij=0; 2、 向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动 个元素。 3、把递归算法改为非递归算法，通常需要增加使用一个 的存储结构。 4、两个串相等的充分必要条件是 。 5、对一个下三角矩阵A，采用压缩存储方式存储在一维数组S1.n*(n+1)/2中（以行序为主序，且A00=S1）,则Aij对应S中的位置是 。 6、已知一棵树边的集合是,。那么根结点是 ，结点g的双亲是 ，结点c的子孙有 ，树的深度是 ，树的度是 ，结点h的层次是 。 7、n个顶点的连通图至少有 条边。 8、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，不稳定的排序有 等几种。三. 分析计算题（每题5分，共20分）1、简述以下关于二叉树某操作的算法的功能和主要思想。 typedef struct BiTNode char data ; / 结点信息是字符 struct BiTNode *lchild,*rchild; / 左右孩子指针 *BiTree;Status xxxx (BiTree T, Status(*Visit)(char e) TStack S; BiTree p; InitStack(S); if(T) Push(S,T); while (!StackEmpty(S) Pop(S,p); Visit(p-data); if(p-lchild) Push(S,p-lchild); if(p-rchild) Push(S,p-rchild); return OK; 2、令有串u=”baabaca”和v=”abcaabbaabcabaabc”，分别求出u,v作为模式串时在KMP算法中各自的nextj值（如下面表1和表2所示）。j1234567ujbaabacanextj 表1j1234567891011121314151617vjabcaabbaabcabaabcnextj 表2 3、设无向网络图G的邻接