华中师范大学网络学院数据结构试题库及答案.doc

《华中师范大学网络学院数据结构试题库及答案.doc》由会员分享，可在线阅读，更多相关《华中师范大学网络学院数据结构试题库及答案.doc（51页珍藏版）》请在三一文库上搜索。

1、华中师范大学网络学院数据结构试题库及答案一、选择题1 在数据结构中，从逻辑上可以把数据结构分成（ ）。A 动态结构和静态结构 B 紧凑结构和非紧凑结构C 线性结构和非线性结构 D 内部结构和非内部结构2 算法分析的目的是（ ）；. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 3. 算法分析的两个主要方面是（ ）。A. 空间复杂度和时间复杂度 B. 正确性和简单性 C可读性和文档性 D. 数据复杂性和程序复杂性4一个顺序表（即顺序存储的线性表）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

2、A 100 B 108 C 100 D 1205在一个长度为n 的顺序表中，向第i个元素（1 i n）之前插入一个新元素时，需要向后移动（ ）个元素。 A.n-i B.n-i-1 C.n-i+1 D.i6从一个长度为n 的顺序表中删除第i个元素（1 i n）时，需要向前移动（ ）个元素。 A.n-i B.n-i-1 C.n-i-1 D.i7若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（ ）.O(n) B.O(n*n) C.O(nlog2n) D.O(log2n)8线性表的存储结构是一种（ ）的存储结构A 随机存取 B 顺序存取 C 索引存取 D HASH

3、存取9. 线性表的链式存储结构是一种（ ）的存储结构。A 随机存取 B 顺序存取 C 索引存取 D HASH存取10若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是（ ） A112 B.144 C.148 D.41211若频繁地对线性表进行插入和删除操作，该线性表应该采用（ ）存储结构。 A散列 B.顺序 C.链式 D.任意 12线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）。A 必须是连续的 B 部分地址必须是连续的C 一定是不边疆的 D 连续不连续都可以13在非空线性链表中，在由p所指的链结点后面插入一个由q所指的

4、链结点的过程是依次执行（ ）Aq-next=p; p-next=q;Bq-next=p-next; p-next=q;Cq-next=p-next; p=q;Dp-next=q; q-next=p;14若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行( )Ar=p-next; p-next=r; call RET(r)Br=p-next; p-next=r-next; call RET(r)Cr=p-next; p-next=r-next; call RET(p)Dp-next=p-next-next; call RET(p)15删除一个双链表中结点p(非头结点和尾结点)的操作

5、是( ). A. p-left-right=p-left;p-right-left=p-right B. p-left-right=p-right;p-right-left=p-ieft C. p-left=NULL;p-right=NULL D. p-right-left=p;p-left-right=p16在一个双链表中结点p之后插入一个结点s的操作是( )。 A. s-right=p;s-left=p-right;p-right-left=s;p-right=s B. s-right=p-right;p-right-left=s;s-right=p;p-left=s C. s-right

6、p-right;s-left=p;p-left-left=s;p-right=s D. s-right=p;p-left-left=s;p-right=s;s-right=p-right17 非空的循环单链表head的尾结点（由p所指向）满足（ ）。A.p-next=NULL; B.p=NULL;C.p-next=head; D.p=head;18 在循环双链表的p所指结点之后插入s的操作是（ ）。A.p-right=s;s-left=p;p-right-left=s;s-rigth=p-right;B.p-right=s;p-right-left=s;s-left=p;s-right=p-

7、right;C.s-left=p;s-right=p-right;p-right-left=s;D.s-left=p; s-right=p-right; p-right-left=s; p-right=s;19设单链表中结点的结构为(data,link)已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作? ( ) A. s-link=p-link;p-link=s; B. q-link=s;s-link=p; C. p-link=s-link;s-link=p; D . p-link=s;s-link=q; 20 设单链表中结点的结构为(dat

8、a,link).已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作?( ) A. s-linkp; p-link=s; B. s-link=P-link; P-link=s; C. s-linkp-link; p=s; D. p-link=s; s-link=p;21设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继,则应执行下列哪个操作? ( )A. p-link=p-link-.link;B. p=p-link=p-link-link;C.p-link=p-link;D. p=p-link-link;22设单循环链表中结点的结构为(date，

9、link)且rear是指向非空的带表头结点的单循环链表的尾结点指针。若想删除链表的第一个结点,则应执行下列哪一个操作?( )A.s=rear;rear=rear-link;delete s; B.rear=rear-link;delete rear;C.rear=rear-link-link;delete rear; D. s=rear-link-link;rear-link-link=s-link;delete s;23设双向循环链表中结点的结构为(data，1Link，rLink)，且不带裹头结点若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作? ( ) A. p-rLi

10、nks; s-1Linkp; p-rLink一-1Links;s-rLink=p-rLink; B. p-rLinks;p-rLink-1Links;s-1Linkp; s-rLinkP-rLink， C. s-1LinkP;s-rLinkp-rlink; P-rLink=s;p-rlink-lLink=s; D. s-1LinkP;s-rLinkp-rLink;P-rLink-1Links;p-rLinks;24数组通常具有的两种基本操作是（ ）。 A建立与删除 B索引和修改 C查找和修改 D查找与索引25二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到8，

11、列下标j的范围从1到10，则存放M至少需要（ ）个字节 A90 B180 C240 D54026二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素（ ）的起始地址相同。 AM24 BM134 CM35 DM14427数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（ ）。 A80 B100 C240 D27028数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址

12、SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（ ）。 ASA+141 BSA+144 CSA+222 DSA+22529数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A518的起始地址为（ ）。 ASA+141 BSA+180 CSA+222 DSA+22530下面的说法中，不正确的是（ ）。 A数组是一种线性表结构 B数组是一种定长的线性表结构， C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作31设

13、矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B1.n(n-1)2中，对任一下三角部分元素ai,j(i)，在一组数组B的下标位置k的值是（ ）。 Ai(i-1)2+j-1 Bi(i-1)2+j Ci(i+1)2+j-1 Di(i+1)2+i32下面的说法中，不正确的是（ ）。 A只须存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B只须存放对角矩阵中的非零元素即可 C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储33对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。 A表达

14、变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销34若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了( )个数组元素。 An/2 Bn*(n-1) Cn*(n+1)2 Dn*(n-1)35若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(it!=0 BSTt= =0 CSTt!=m0 DSTt= =m047判定一个栈ST(最多元素为m0)为栈满的条件是( )。 ASTtop!=0 BSTtop= =

15、0 CSTtop!=m0 DSTtop= =m048 一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。 Aedcba Bdecba Cdceab Dabcde49 一个栈的人栈序列是l，2，3，4，则栈的可能的输出序列是( )。 A1，4，2，3 B2，1，4，3 C。4，2，1，3 D4，2，3，l50若己知一个栈的人栈序列是1，2，3，,n，其输出序列为p1,p2,p3, ,pn，若p1则pi为（ ）Ai Bn=i Cn-i+1 D不确定51. 若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是（ ）。 A. 不变 B.top 0 C.t

16、op top-1 D.top top+152向一个栈顶指针为HS的链栈中插入个s所指结点时，则执行( ) AHS-next=S； BS-next=HS-next；HS-next=S； CS-next=HS；HS=S； DS-next=HS；HS=HS-next；53从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行( )。 AX=HS；HS=HS-next； BX=HS-data； CHS=HS-next；K=HS-data； Dx=HS-data；HS=HS-next54中缀表达式A-(B+CD)*E的后缀形式是( )。 AABC+D*E- BABCD+E*- CAB-

17、C+DE* DABC-+D/E*55. 若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个数据信息为item的新元素的过程式依次执行：call GETNODE(p),data(p) item, ( ),top p. A. p top B. top p C.link(p) top D.link(top) p56若某堆栈的输入序列为1，2，3，n-1，n，输出序列的第1个元素为n，则第i个输出元素为( )。 A. n-i+l Bn-i Ci D哪个元素无所谓57 一个队列的人列序列是1，2，3，4，则队列的输出序列是( )。A4，3，2，1 B1，2，3，4 C。1，4，3，2 D3，2，4

18、l58 判定一个队列QU(最多元素为m0)为空的条件是( )。 AQUrear-QUfront= =m0 BQUrearQUfront1= =m0 CQUfront= =QUrear DQUfront= =QUrear+l59判定一个队列QU(最多元素为m0)为满队列的条件是( )。 AQU-rear-QU-front=mO BQU-rear-QU-front-1=m0 CQU-front=QU-rear DQU-front=QU-rear+l60判定一个循环队列QU(最多元素为m0)为空的条件是( )。 AQU-front=QU-rear BQU-front!=QU-rear CQU-fr

19、ont=(QU-rear+1)m0 DQU-front!=(QU-rear+1)m061判定一个循环队列QU(最多元素为m0)为满队列的条件是( ) AQU-front=QU-rear BQU-front!=QU-rear CQU-front=(QU-rear+1)m0 DQU-front!=(QU-rear+1)m062表达式a*(b+c)-d的中缀表达式是( ) A. abcd*+- Babc+*d Cabc*+d- D-+*abcd63在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲

20、区应该是一个( ) 结构。 A线性表 B数组 C堆栈 D队列64设计一个递归问题的非递归算法通常需要设置( )结构。A线性表 B数组 C堆栈 D队列65. 队列是限定在( )处进行插入操作的线性表 A. 任意端点 B. 队头 C. 队尾 D. 中间 66. 队列是限定在( )处进行删除操作的线性表A. 任意端点 B. 队头C. 队尾 D. 中间 67. 队列中元素的个数是( )A. 不变的 B. 可变的C. 任意的 D. 068递归函数f(n)=f(n-1)十n(n1)的递归出口是( )。Af(1)=0 Bf(1)=1 Cf(0)=1 Df(n)=n69 广义表中元素分为（ ）A原子元素 B.

21、表元素C原子元素 D.任意元素70 广义表的长度是指（ ）A，广义表中元素的个数 B。广义表中原子元素的个数C广义表中表元素的个数 D广义表中括号嵌套的层数71. 广义表的深度是指 ( )A广义表中元素的个数 B广义表中原子元素甜个数C.广义表中表元素的个数 D广义表中括号嵌套的层数72广义表A：)，(a)，b，left!=NULl Ct-ltag=0 Dt-ltag=194在线索二叉树中，t所指结点没有左子树的充要条件是( )。 At-left=KTULL Bt-ltag=1 Ct-ltag=1且t-left=NULL D以上都不对95. 若由树转化得到的二叉树是非空的二叉树，则二叉树形状是

22、 ）A 根点无右子树的二叉树B 根结点无左子树的二叉树C根结点可能有左二叉树和右二叉树D 各结点只有一个儿子的二叉树96. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）A 根结点无右子树的二叉B 根结点无左子树的二叉树C 根结点可能有左二叉树和右二叉树D 各结点只有一个儿子的二叉树97. 判定树中仅（ ）结点包含一个条件。A非终端 B 终端 C 根 D 所有98. 哈夫曼树是访问叶子结点的外部路径长（ ）的二叉树. 最短 . 最长 . 可变 . 不定99. 若TD(vi)表示具有n个顶点、e条边的图中顶点vi的度，那么，TD(vi)与n和e者之间的关系为( )。 n A. e

23、nxTD(vi) Be=nxTD(vi) i=1 n n C. e=2xTD(vi) D2xe=TD(v1) i=1 i=1100一个具有n个顶点的无向图最多有( )条边。 Anx(n-1)2 Bnx(n-1) Cnx(n+1)2 Dnxn101一个具有n个顶点的有向图最多有( )条边。 Anx(n-1)2 Bnx(n-1) Cnx(n+1)2 Dnxn102具有6个顶点的无向图至少应该有( )条边才能保证是一个连通图。 A4 B5 C6 D7103，一个有n个顶点的无向图最多有( )条边。 An Bn(n一1) Cn(n一土)2 D2n 104. 具有4个顶点的无向完全图有( )条边。 A

24、6 B12 C16 D20105. 具有6个顶点的无向图至少应有( )条边才能确保是一个连通图。 A5 B6 C7 D。8106.以下叙述中正确的是( )。A图G的某一最小生成树的代价一定小于其他生成树的代价B若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条C 任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条D有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第主列的元素个数107. 对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少3一个无向图采用邻接矩阵存储方

25、法，其邻接矩阵一定是一个( )。A对称矩阵 B对角矩阵C三角矩阵 D稀疏矩阵108. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。An B(n一1)*(n一土) Cn一1 Dn*n109.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( )。An Bn+1 Cn-l Dn十e110图的深度优先搜索算法类似于二叉树的( )。 A前序遍历 B中序遍历 C后序遍历 D按层次遍历111图的广度优先搜索算法类似于二叉树的( )。 A前序遍历 B中序遍历 C后序遍历 D按层次遍历112导致图的遍历序列不惟一的因素是( )。 A出发点的不同、遍历方法

26、的不同 B出发点的不同、存储结构的不同 C遍历方法的不同、存储结构的不同 D出发点的不同、存储结构的不同、遍历方法的不同113已知带权连通无向图G=(V，E)，其中V=v1，v2，v3，v4，v5，v6，v7，E=(v1，v2)l0，(v1，v3)2，(v3，v4)2，(v3，v6)11，(v2，v5)1，(v4，v5)4，(v4，v6)6，(v5,v7)7，(v6，v7)3(注：顶点偶对右下角的数据为边上的权值)，从源点v1到顶点v7的最短路径上经过的顶点序 列是( )。 A. v1，v2，v5，v7 Bv1，v3，v4，v6，v7 C. V1，V3，V4，V5，V7 DV1，V2，V5，V

27、4，V6，V7114. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A先序遍历 B中序遍历 C后序遍历 D按层遍历115. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )。A先序遍历 B中序遍历 巳后序遍历 D；按层遍历 116任何一个带权无向连通图的最小生成树( )。 A是唯一的 B是不唯一的 C有可能不惟一 D有可能不存在117 带权连通图G=(V，E)，其中V=v1，v2，v3，v4，v5,E=(v1，v2)7，(v1，v3)6 ,(v1 v4)9，(v2，v3)8，(v2，v4)4，(v2，v5)4，(v3，v4)6，(v4，v5)2(注：顶点偶对右下角的数据为

28、边上的权值)，G的最小生成树的权值之和( )。A16 B17 C18 D.19118判定一个有向图中是否存在回路可以利用( )方法。A. 求最小生成树 B求最短路径C拓扑排序 D图的遍历119. 任何一个无向连通图的最小生成树( )。A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在120. 最小生成树的构造可使用（ ）算法。A. 普里姆算法B. 克鲁斯卡尔算法C. 迪杰斯特拉算法D. 哈夫曼算法121. 任何一个带权的无向连通图的最小生成树（ ）（A） 只有一棵（B） 有一棵或多棵（C） 一定有多棵（D） 可能不存在122. 含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）A. 1 B. N/2 C. N-1 D. N123判定一个有向图中是否存在回路除了利用拓扑排序方法以外，还可