20101月数据结构答案、解析
做试题,没答案?上自考365,网校名师为你详细解答!
全国2010年1月自学考试数据结构试题
课程代码：02331
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（）
A．问题规模B．语句条数
C．循环层数D．函数数量
答案：A
解析：常识问题
2．具有线性结构的数据结构是（）
A．树B．图
C．栈和队列D．广义表
答案：C
解析：顺序表、单链表、双链表、循环链表、栈和队列等都是1:1关系，是线性的。
树：结点之间1：n关系，非线性的。广义表和图是m:n关系，非线性的。
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（）
A．O(1) B．O(m)
C．O(n) D．O(m+n)
答案：B
解析：链表A与链表B连接问题，可以这样考虑，链表A和链表B，我们只知道其头指针或头结点，我们连接是把链表A的尾部连接到链表B的头部，要知道链表A的尾部，就必须从链表A的头部做m次判断，得到链表A的尾部，然后直接和链表B的头部连接就可以了。(原来链表A的尾部是指向NULL的，连接链表B就是把链表A尾部的NULL改为链表B的头结点的指针。)
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（）
A．2个B．3个．
C．4个D．6个
答案：C
解析：双向循环链表中结点与结点之间有4条线，所以插入一个新结点，需要修改指针域的数量为4条。5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（）
A．3 B．37
C．50 D．97
答案：B
解析：循环队列，front=47,则rear=(front+队列元素个数)%数组长度=(47+50)%60=37。
6．若栈采用链式存储结构，则下列说法中正确的是（）
A．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空
答案：B
解析：链栈由于采用链表方式作为存储方式，入栈时，使用malloc申请空间后，用指针相连接，所以结点个数没有限制，但是出栈时，如果栈中的元素个数为0，就不能再出栈了。
7．若串str=”Software”，其子串的数目是（）
A．8 B．9
C．36 D．37
答案：D
解析：字串包括：单字符的字串：”S”、”o”等共8个，2个字符的字串”So”、”of”共7个，3个字符的字串”Sof”、”oft”等共6个，以此类推，可以知道总数量S=8+7+6+5+4+3+2+1=（1+8）*8/2=36。最后别忘记了，空串””是任何字符串的字串，所以S=36+1=37.
结论：求字符串的子串个数公式：S=(1+字符串长度)* 字符串长度/2+1
8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，a ll为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（）
A．1012 B．1017
C．1032 D．1039
答案：C
解析：按行优先压缩，每一行10个元素。又由于下标从1开始且是下三角，所以a85的前7行共有1+2+3+4+5+6+7=(1+7)*7/2=28个元素，第8行不满，列5前有5-1=4个元素，所以a85前共有28+4=32个元素。又由于每个元素占一个地址单元，所以a85的地址=a11+32个元素的地址增量=1000+32*1=1032。9．允许结点共享的广义表称为（）
A．纯表B．线性表
C．递归表D．再入表
答案：D
解析：没有共享结点，没有递归结点的表是纯表。有共享结点的表是再入表，有递归结点的表是递归表。10．下列数据结构中，不属于二叉树的是（）
A．B树B．AVL树
C．二叉排序树D．哈夫曼树
答案：A
解析：根据概念可以得到答案。
11．对下面有向图给出了四种可能的拓扑序列，其中错误
．．的是（）
A．1，5，2，6，3，4 B．1，5，6，2，3，4
C．5，1，6，3，4，2 D．5，1，2，6，4，3
答案：C
解析：根据先找没有前驱的结点的方式，找到没有前驱的结点后，后删除该结点上的连线，可以推出C是错误的。
12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（）
A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v4
答案：D
解析：从V1出发，根据标号最小原则，深度遍历后，容易得出D是正确的。
具体遍历方式为：V1->v2->v5->v6，v6没有出度，返回v5，v5->v7，v7没有出度，返回v5，v5的2个出度(v6和v7)都已经遍历，返回v2，v2的2个出度(v5和v6)都已经遍历，返回v1，v1->v3，v3没有出度，返回v1,v1->v4，所以最后的遍历序列为v1->v2->v5->v6->v7->v3->v4。
13．下列排序算法中不稳定的是（）
A．快速排序B．归并排序
C．冒泡排序D．直接插入排序
答案：A
解析：稳定的排序算法共有4个，直插、冒泡、归并、基数，其他的都是不稳定的。
14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（）
A．2 B．3
C．4 D．8
答案：B
解析：第一次查找取mid=(low+high)/2=(1+13)/2=7,如果数组名为R，则R[7]=45，32比45小，则应该在前半部分再找，所以high=mid-1=6。
第二次查找取mid=(low+high)/2=(1+6)/2=3,则R[3]=9,9比32小，应该在后半部分找。所以low=mid+1=4。第三次查找mid=(low+high)/2=(4+6)/2=5,则R[5]=32,32==32成立，找到了。
总共查找了3次。
15．采用ISAM组织文件的方式属于（）
A．链组织B．顺序组织
C．散列组织D．索引组织
答案：B
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16．数据元素及其关系在计算机存储器内的表示称为_________。
答案：存储结构。
解析：数据结构包括三个部分：逻辑结构、存储结构、算法。
17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。答案： i
解析：由于单链表查找，必须从头指针或头结点开始查找。查找第一个元素时需要的时间为1次，查找第二个元素需要判断的时间为2次，…以此类推，查找第i个元素的时间为i次。
18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。
typedef struct{
DataType data[100]；
int top；
}SeqStack；
DataType f18(SeqStack*S)
{ if(StackEmpty(S))
Error(”Stack is empty”)；
return S->data[S->top]；
}
答案：取栈顶元素或取栈顶元素的值
解析：前面是栈的定义，函数f18中，最后一句return s->data[s->top] 。s->top是栈顶的位置，s->data[X]，表示栈的X位置上的元素值。
19．在串匹配中，一般将主串称为目标串，将子串称为_________。
答案：模式串
解析：概念题，记住它。
20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= _________。
答案： ()
解析：从最里面开始，tail(C)→(d),head(tail(C))→d,tail(head(tail(C))) →()。
21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_________。
答案： 219
解析：这6个结点作为哈夫曼树的叶子，先选取2个最小的值作为叶子，生成一个根，…可以得到最后的哈夫曼树，算一下就知道答案了。长度=6*4+7*4+13*3+16*2+18*2+30*2=219 。
22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。
答案： 35
解析：由最短路径的算法，可以得出A->D->E->C是最短路径，路径长度为2+21+12=35。
23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。
答案： 42,13,94,55,05,46,17
解析：从个位数开始排，就可以得到答案序列。
24．高度为3的3阶B-树最少的关键字总数是_________。
答案： 7
解析： B树的定义如下：
一棵m阶的B-树满足下列条件：
(1)树中每个结点至多有m个孩子；
(2) 除根结点和叶子结点外，其它每个结点至少有┌m/2┐个孩子；
(3)若根结点不是叶子结点，则至少有2个孩子；
(4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；
(5) 有k个孩子的非终端结点恰好包含有k-1个关键字。
解题思路：
(1)根据树的性质可以知道根只有一个。Count=1.
(2)根据性质(3),3阶B树的根不是叶子，至少有2个孩子。Count=1+2=3
(3)根据性质(2)，可以知道第2层中的每个结点，每个结点至少有┌m/2┐个孩子，即2个孩子；所以第三层上有4个结点。Count=1+2+4=7个结点。且每个结点中只包含1个关键字。
25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。
三、解答题(本大题共4小题，每小题5分，共20分)
26．假设二叉树的RNL遍历算法定义如下：Array若二叉树非空，则依次执行如下操作：
(1)遍历右子树；
(2)访问根节点；
(3)遍历左子树。
已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。
答案： G,C,F,A,B,D。
解析：根据定义，比较容易得到该序列。实质上是前序序列的倒转。
27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。
请回答下列问题：
(1)请画出对应的图G。
(2)画出图G的邻接表存储结构。
答案：如图所示。
解析：通过矩阵中的1就可以知道哪个结点与哪个结点之间的连线。得到图之后，生成邻接表很容易的。28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。
答案：序列为(12,15,14,18,16,36,18,60,25,85)。
解析：如上图所示先构造出出示的完全二叉树，如左图所示，然后先从最后一个非叶子结点开始调整，结点顺序，一定要满足小根堆的性质，以此类推，调整完毕后如右图所示，就是小根堆，写出序列后就是了。
29．已知一棵二叉排序树如图所示。
请回答下列问题：
(1)画出插入元素23后的树结构；
(2)请画出在原图中删除元素57后的树结构。
答案：(1)插入元素23后，二叉排序树变成如图中的左图所示。 (2)删除元素57后，二叉排序树变成如图所示的右图所示。
解析：(1)新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点
的左孩子或右孩子结点。
（2）二叉排序的删除。分三种情况：
<1>若被删除的结点p 是叶子，则直接删除就可以了。
<2>若被删除的结点p 不是叶子，但p 只有左子树或右子树，则将p 的左子树或右子树直接修改为p 的双亲的子树即可。
<3>若被删除的结点p 不是叶子，但p 既有左子树，也有右子树，此时需用结点p 的(中序)直接前驱或直接后继代替p ，然后再从二叉排序树中删除p 的直接前驱或直接后继。
本题中的结点57既有左孩子又有右孩子，需找到它的直接前驱结点49。用49直接替代57。然后删除49即可。
四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．已知下列程序，Ls 指向带头结点的单链表。 Typedefstruct node { DataType data; struct node * next; } * LinkList;
void f30( LinkList Ls )
{ LinkList p, q;
q = Ls->next;
if ( q && q->next ) {
Ls->next = q->next;
p=q
while ( p->next )
p = p->next;
p->next = q;
q->next = NULL;
}
}
请回答下列问题：
(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。
(2)请简述算法的功能。
第二步的答案如下：通过结果可以推出，该算法的功能是把第一个结点(开始结点)移动到链表的尾部。
解析：根据程序可以很容易的得到如上图所示的结果。第二步的答案是非常明显的。
31．已知字符串处理函数f31程序如下。
int f31(char*strl，char*str2)
{ while(*strl==*str2&&(*strl!=’＼0’)){
strl++；
str2++；
}
return(*strl-*str2 ? l∶0)；
}
请回答下列问题：
(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是
f31(”abcde”，”abcde”)，则函数的返回值是什么?
(2)简述该函数的功能。
答案：（1）1 0
（2）判断字符串是否相等，如果相等返回0，否则返回1。
解析：程序比较简单，关键是理解*str1的作用是什么？通过函数的参数可以得知str1和str2是分别指向字符串的指针，也就是保存字符串的数组的开始地址，程序中的*str1的功能是求某当前地址下的字符的值。因此，实参为f31(”abcde”，”abcdf’)时，要以此判断a==a成立，b==b成立，以此类推，只到e==f不成立结束。循环结束后，return(*strl-*str2 ? l∶0)；即return (‘e’-‘f’?1:0)，e-f 不等于0表示条件成立，成立则返回1。故f31(”abcde”，”abcdf’)返回1。
f31(”abcde”，”abcde”)，循环条件结束时，*str1的值为’\0’,*str2的值也是’\0’,所以return(*strl-*str2 ? l∶0)，即return(‘\0’-‘\0’?1:0)，’\0’-‘\0’等于0，0表示不成立，不成立取第二个表达式的值0，所以f31(”abcde”，”abcde”)返回值为0。
第二部答案：通过分析很容易得出。
32．数组A[]中存储有n个整数，请阅读下列程序。
void f32(intA[]，int n)
{ inti，j，k，x；
k=n-l；
while(k>0){
i=k； k=0；
for(j=O；j if(A[j]>A[j+1]){ x=A[j]； A[j]=A[j+l]； A[j+1]=x； k=j； }／／end of if }／／end of while return； } 请回答下列问题： (1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? (2)说明该算法的功能。 答案：(1)数组A中的结果{2,4,6,7,8,10} (2)该算法的功能是对数组进行A中的前n个元素进行冒泡排序。 解析：通过将数组A和6带入后，很容易分析出结果。 33．下面程序实现二分查找算法。 Typedef struct{ KeyType key； InfoType otherinfo； }SeqList[N+1]； int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) ){ mid=(1ow+high)／2； if( (2) ) return mid； if(R[mid]．key>K) high=mid-1； else (3) ； } return O； } ／／BinSearch 请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3) 答案：(1)low<=high (2)R[mid]==k (3)low=mid+1 解析：二分法查找是必须要掌握的，基本上格式是固定的。只要理解什么是二分法，比较容易得出答案。 五、算法设计题(本题10分) 34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ ElmType data； struct Node *lchild，*rchild； }*BiTree； 请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。 答案： int SumNodes(BiTree T) { int count=0; /*count表示树T中全部结点的个数，初始值为0*/ if(T->lchild==NULL && T->rchild==NULL) /*递归结束条件*/ { count=1; return count; } else /*else后面的代码是递归公式,分三种情况，具体见解析部分*/ if(T->lchild!=NULL && T->rchild==NULL) /*表示只有左子树*/ count=1+SumNodes(T->lchild); /*其中1表示根结点的数量*/ else if(T->lchild==NULL && T->rchild!=NULL) /*表示只有右子树*/ count=1+SumNodes(T->rchild); /*其中1表示根结点的数量*/ else if(T->lchild!=NULL && T->rchild!=NULL) /*既有左子树，又有右子树*/ count=1+SumNodes(T->lchild)+SumNode(T->rchild); } 解析：(一)函数定义中的头部分析。 通过题目意思可以得到，我们要写一个函数，函数名为SumNodes()，里面有一个参数BiTree类型的T，该函数是有返回值的，返回值为树T的结点总数，返回值的类型为int，所以函数的类型也为int(因为返回值的类型就是函数的类型)。 通过上面的分析可以定义如下： Int SumNodes(BiTree T) { } (二)函数定义中的函数体分析 题目要求用递归算法，递归算法的关键点有2个：一个是递归结束条件，一个是递归公式。 (1)递归结束条件，根据树的特点我们可以知道如果树T的某个结点，没有左孩子同时也没有右孩子，即该结点是叶子结点，叶子结点可以理解为一颗只有1个结点的树,我们可以确定该叶子结点组成的树只有1个结点。 所以递归结束条件为: if(T->lchild==NULL && T->rchild==NULL) { count=1; return count; } (2)递归公式，如果某结点不是叶子结点，不是叶子结点有三种情况，a.只有左孩子；b.只有右孩子； c.既有左孩子又有右孩子。a这种情况，可以确定1个结点，即根结点，其他的结点树需继续执行本函数，参数为左孩子的地址。b这种情况,可以确定1个结点，即根结点，其他的结点数需继续调用本函数，参数为右孩子的地址。c这种情况,可以确定一个结点，即根结点,其他的结点数需继续调用本函数，且需要调用2次本函数，参数分别为左孩子地址，右孩子地址。 即递归公式为： if(T->lchild!=NULL && T->rchild==NULL) /*表示只有左子树*/ count=1+SumNodes(T->lchild); /*其中1表示根结点的数量*/ else if(T->lchild==NULL && T->rchild!=NULL) /*表示只有右子树*/ count=1+SumNodes(T->rchild); /*其中1表示根结点的数量*/ else if(T->lchild!=NULL && T->rchild!=NULL) /*既有左子树，又有右子树*/ count=1+SumNodes(T->lchild)+SumNode(T->rchild); 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结 点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系 C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理 C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 数据结构习题 第一章绪论 1.1数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。 ①A.数据元素B.计算方法C.逻辑存储D.数据映像 ②A.结构 B.关系 C.运算 D.算法 1.2 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求该进 D.分析算法的易懂性和文档性 ② A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 1.3 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 ② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C.确定性、有穷性和可行性 D.易读性、稳定性和安全性 1.4数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。 1.5数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。 1.6 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。 1.7 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。 1.8顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。 第二章线性表 2.1 链表不具备的特点是____ 。 A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 2.2 不带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head !=null 2.3带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head!=null 2.4 非空的循环单链表head 的尾结点（由p所指向）满足____。 A. p->next==null B. p==null C. p->next==head D. p==head 2.5 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 2.6线性链表中各个结点之间的地址不一定连续。 2.7线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个后 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（√） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√） 7.数据的存储结构是数据的逻辑结构的存储映像。（×） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和的描述步骤。（√） 填空题： 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面 的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的 有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算和事后统计法。 16.一个算法的时间复杂性是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题 规模n的函数。 18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n ）。 若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。 数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。 19.串的两种最基本的存储方式是顺序存储方式链式存储方式。 20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_____数据元素的有限集____的集合D和D上____关系的有限集_____的集合R所构成的二元组：DS=（D，R）。 3． 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为 ____O(log2n)_______；成平方关系时，则表示为____O(n2)______。 5．数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。 6．线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。 7．树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。 8．图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 数据结构习题集(自编) 第一章绪论 一、选择题 1.数据结构就是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的()与运算的学科。 A.结构 B.关系 C.运算 D.算法 2.在数据结构中,从逻辑上可以把数据结构分成()。 A.动态结构与静态结构 B.紧凑结构与非紧凑结构 C.线性结构与非线性结构 D.逻辑结构与存储结构 3.线性表的逻辑顺序与存储顺序总就是一致的,这种说法()。 A.正确 B.不正确 C.无法确定 D.以上答案都不对 4.算法分析的目的就是()。 A.找出算法的合理性 B.研究算法的输人与输出关系 C.分析算法的有效性以求改进 D.分析算法的易懂性 5、算法的时间复杂度取决于( ) A.问题的规模B待处理数据的初态 C、 A与B 6.一个算法应该就是( )。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A与C、 7、下面关于算法说法错误的就是( ) A.算法最终必须由计算机程序实现 B、为解决某问题的算法与为该问题编写的程序含义就是相同的 C、算法的可行性就是指指令不能有二义性 D、以上几个都就是错误的 8.以下与数据的存储结构无关的术语就是( )。 A.循环队列 B、链表 C、哈希表D、栈 9.在下面的程序段中,对x的赋值语句的频度为( ) for(i=0;i 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={ 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 数据结构题集答案 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【 A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【 C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【 D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【 A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 第7章图 一、单选题 01、在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2 B．1 C．2 D．4 02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A．1/2 B．1 C．2 D．4 03、有8个结点的无向图最多有条边。 A．14 B．28 C．56 D．112 04、有8个结点的无向连通图最少有条边。 A．5 B．6 C．7 D．8 05、有8个结点的有向完全图有条边。 A．14 B．28 C．56 D．112 06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A．O(n) B．O(e) C．O(n+e) D．O(n2) 09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2 10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6 C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 6 11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历15、任何一个无向连通图的最小生成树。 A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在 ( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A．n、2e B．n、e C．n、n+e D．2n、2e 17、判断有向图是否存在回路，可以利用算法。 A．关键路径 B．最短路径的Dijkstra C．拓扑排序D．广度优先遍历 18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 19、求最短路径的Dijkstra算法的时间复杂度是___。A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。 A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。 A．第i行非∞的元素之和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 22、一个有n个顶点的无向图最多有条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 A．n B．(n-1)2 C．n-1 D．n2 24、对某个无向图的邻接矩阵来说，。 A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数 25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2数据结构习题解答
数据结构题集c语言版答案严蔚敏吴伟民[1]
数据结构习题集(答案)
数据结构模拟试题及答案
数据结构习题与答案
数据结构复习题附答案
数据结构题集与答案
数据结构习题集
数据结构习题集包含全部答案
《数据结构》期末考试题及答案
数据结构习题集(积分)
最新数据结构习题集答案解析--清华大学版
数据结构模拟卷(含答案)经典习题培训讲学
数据结构题集答案复习过程
最新数据结构习题与答案--图
数据结构模拟卷(含答案)经典习题
相关文档
- 数据结构习题集(答案)
- 数据结构习题集答案C语言版
- 数据结构习题集答案解析--清华大学版
- 数据结构习题与答案
- 数据结构习题集包含全部答案
- 数据结构习题和答案及解析
- 数据结构习题集答案
- 数据结构习题集答案(c版)(清华大学 严蔚敏)
- 数据结构习题集答案(c版)(清华大学-严蔚敏)
- 最新数据结构习题与答案--图
- 清华数据结构习题集答案
- 数据结构练习题及答案 清华出版社
- 数据结构习题集(答案)
- 清华数据结构习题集答案(C语言版严蔚敏)
- 数据结构习题集(答案)
- 数据结构习题集答案(c版)(清华大学严蔚敏)
- 数据结构习题及解答
- 数据结构习题集答案_C语言版(严蔚敏 吴伟民)
- 数据结构习题及参考答案
- 数据结构习题集和答案