智慧树知到《数据结构（中国海洋大学）》章节测试答案
智慧树知到《数据结构（中国海洋大学）》章节测试答案
第一章单元测试
1、图书馆的数目检索系统采用（）关系的数据结构。
A.集合
B.线性
C.树形
D.图状
正确答案：线性
2、（）是相互之间存在一种或多种特定关系的数据元素的集合。
A.数据
B.数据元素
C.数据项
D.数据结构
正确答案：数据结构
3、（）是一个值的集合和定义在这个值集上的一组操作的总称。
A.数据类型
B.数据元素
C.数据项
D.数据结构
正确答案：数据类型
4、算法的确定性是指（）
A.当输入数据非法时，算法也能作出反应或进行处理
B.在任何情况下，算法不会出现死循环
C.算法中的每一条指令必须有确切的含义
D.算法中没有逻辑错误
正确答案：算法中的每一条指令必须有确切的含义
第二章单元测试
1、线性表中的数据元素有一个前驱多个后继。
A.正确
B.错误
正确答案：错误
2、用顺序结构存储，删除最后一个结点时，（）
A.会移动其它结点位置
B.一定不会移动其它结点位置
C.可能会移动其它结点位置
D.其它
正确答案：一定不会移动其它结点位置
3、链表中逻辑上相邻的元素的物理地址（）相邻。
A.必定
B.不一定
C.一定不
D.其它
正确答案：不一定
4、1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose（）L（LinkList &；A，LinkList &；B，LinkList &；C）{； LinkList pa，pb，qa，qb； pa=A； pb=B； qa=pa； //保存pa的前驱指针； qb=pb； //保存pb的前驱指针； pa=pa->；next； pb=pb->；next； A->；next=NULL； C=A； while（pa&；&；pb）{； if（pa->；data<；pb->；data）{； qa=pa； pa=pa->；next； qa->；next=A->；next； //将当前最小结点插入A表表头； A->；next=qa； }； else{； qb=pb； pb=pb->；next；（）//将当前最小结点插入B表表头； A->；next=qb； }； }； while（pa）{； qa=pa； pa=pa->；next； qa->；next=A->；next； A->；next=qa； }； while（pb）{； qb=pb； pb=pb->；next； qb->；next=A->；next； A->；next=qb； }； pb=B； free（pb）； return OK；}
A.qa->next=A->next
B.qb->next=A->next
C.qa->next=A
D.qb->next=A
正确答案：qb->next=A->next
5、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。StatusListDelete（）CL（LinkList &；S）{； LinkList p，q； if（S==S->；next）return ERROR； q=S； p=S->；next； while（；）{； q=p； p=p->；next； }； q->；next=p->；next； free（p）； return OK；}
A.p->next!=S
B.p->next==S
C.p!=S
D.p==S
正确答案：p->next!=S
第三章单元测试
1、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（）
A.SXSSXXXX
B.SXXSXSSX
C.SXSXXSSX
D.SSSXXSXX
正确答案：SSSXXSXX
2、 设计一个迷宫求解的算法，采用（）数据结构最佳。
A.线性表的顺序存储结构
B.栈
C.队列
D.线性表的链式存储结构
正确答案：栈
3、循环队列存储在数组A[0..m-1]，则出队时的操作为（）
A.front=front+1
B.front=（front+1）mod（m-1）
C.front=（front+1）mod m
D.front=（front mod m）+1
正确答案：front=（front+1）mod m
4、1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&；序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&；’，且序列2是序列1的逆序列。例如，‘a+b&；b+a’是属该模式的字符序列，而‘1+3&；3-1’则不是。BOOLSymmetry（char a[]）{； int i=0； Stack s； InitStack（s）； ElemType x； while（a[i]!='&；' &；&； a[i]）{（）； i++； }； if（!a[i]） return FALSE； i++； while（a[i]）{； Pop（s，x）； if（x!=a[i]）{； DestroyStack（s）； return FALSE； }； i++； }； return TRUE；}
A.Pop（s，a[i++]）
B.Push（s，a[i++]）
C.Push（s，a[i]）
D.Pop（s，a[i]）
正确答案：Push（s，a[i]）
5、Status；SymmetryString（char*；p）{ Queue；q； if（!InitQueue（q））；return；0； Stack；s； InitStack（s）； ElemType；e1，e2； while（*p）{ Push（s，*p）； EnQueue（q，*p）； p++； } while（!StackEmpty（s））{ （）； DeQueue（q，e2）； if（e1!=e2）；return；FALSE； } return；OK；}
A.Pop（s，e1）
B.Push（s，*p）
C.EnQueue（q，*p）
D.P--P--P--P--P--P--P--P--
正确答案：Pop（s，e1）
第四章单元测试
1、设s=’I AM A STUDENT’ ， t=’GOOD’ ，则Concat（Substring（s，6，2），Concat（t，SubString（s，7，8）））=（）
A.A GOODWORKER
B.ST GOODSTUDENT
C.A GOOD STUDENT
D.A GOOD WORKER
正确答案：A GOOD STUDENT
2、空串与空格串是相同的，这种说法（）。
A.正确
B.不正确
正确答案：不正确
3、设串sl=″Data Structures with Java″，s2=“it″，则子串定位函数index（s1，s2）的值为（）。
A.15
B.16
C.17
D.18
正确答案：18
4、串的长度是指（）
A.串中所含不同字母的个数
B.串中所含字符的个数
C.串中所含不同字符的个数
D.串中所含非空格字符的个数
正确答案：串中所含字符的个数
5、串是一种数据对象和操作都特殊的线性表。
A.正确
B.错误
正确答案：正确
第五章单元测试
1、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
A.80
B.100
C.240
D.270
正确答案：240
2、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（）
A.1018
B.1024
C.1030
D.1072
正确答案：1072
3、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。
A.正确
B.错误
正确答案：错误
4、广义表（（），a，（（b，c），（），d），（（（e））））的长度为（）
A.3
B.4
C.5
D.2
正确答案：4
5、下面说法不正确的是（）。
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构
正确答案：广义表的表头总是一个广义表
6、1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。// 由广义表L复制广义表TintCopyGList（GList&； T，GList&； L）{； if（!L） T=NULL； else{； T=newGLNode； if（!T）exit（OVERFLOW）； T->；tag=L->；tag； if（L->；tag==ATOM）T->；atom=L->；atom； else{（）； CopyGList（T->；tp，L->；tp）； }； }； return OK；}
A.
A.CopyGList（T，L）
B.CopyGList（L->tp，T->tp）
C.CopyGList（L->hp，T->hp）
D.CopyGList（T->hp，L->hp）
正确答案：CopyGList（T->hp，L->hp）
第六章单元测试
1、已知一棵树边的集合为{<；I，M>；， <；I，N>；， <；E，I>；， <；B，E>；， <；B，D>；， <；A，B>；， <；G，J>；， <；G，K>；， <；C，G>；， <；C，F>；， <；H，L>；， <；C，H>；， <；A，C>；}，问这棵树中结点G的双亲结点为（）
A.A
B.C
C.I
D.B
正确答案：C
2、 一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为（）
A.9
B.10
C.11
D.12
正确答案：9
3、假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（）
A.结点A是结点D的双亲结点
B.结点A是结点D的右子树上的结点
C.结点A是结点D的左子树上的结点
D.结点A与结点D具有共同的双亲的右子树上的结点
正确答案：结点A是结点D的右子树上的结点
4、已知一棵树边的集合为{<；I，M>；， <；I，N>；， <；E，I>；， <；B，E>；， <；B，D>；， <；A，B>；， <；G，J>；， <；G，K>；， <；C，G>；， <；C，F>；， <；H，L>；， <；C，H>；， <；A，C>；}，将此树转化为二叉树后，E的左孩子为（）
A.A
B.C
C.I
D.B
正确答案：I
5、一棵哈夫曼树有17个结点，则其叶子结点的个数是（）。
A.7
B.8
C.9
D.10
正确答案：9
6、写递归算法，将二叉树中所有结点的左、右子树相互交换。Status ExchangeBiTree（BiTree&； T）{； BiTreep； if（T）{； p=T->；lchild； T->；lchild=T->；rchild； T->；rchild=p； ExchangeBiTree（T->；lchild）；（）；}； returnOK；}
A.
A.ExchangeBiTree（p）
B.ExchangeBiTree（T->rchild）
C.ExchangeBiTree（T->lchild->rchild）
D.ExchangeBiTree（T）
正确答案：ExchangeBiTree（T->rchild）
7、试写一个算法，为一棵二叉树建立后序线索二叉树。StatusPostOrderThreading（BiThrTree&； T，BiThrTree&； pre）；//首先建立后序线索树StatusFindNextInBiThrTree（BiThrTree&； q，TElemType *p）；//再进行查找；// 后序线索二叉树的算法StatusPostOrderThreading（BiThrTree&； Thrt，BiThrTree&； T）{； BiThrTree pre； Thrt=new BiThrNode； // 为线索二叉树建立头结点； if（!Thrt） exit（OVERFLOW）； Thrt->；LTag=Link； Thrt->；RTag=Thread； Thrt->；rchild=Thrt；// 右子树回指； if（!T） Thrt->；lchild=Thrt；// 若二叉树空，左子树回指； else{； Thrt->；lchild=T； pre=Thrt； PostThreading（T，pre）；// 后序遍历进行后序线索化； pre->；rchild=Thrt；//最后一个结点线索化； pre->；RTag=Thread； Thrt->；rchild=pre； }； return OK；}；StatusPostThreading（BiThrTree&； T，BiThrTree&； pre）{； if（T）{； if（T->；LTag==Link）PostThreading（T->；lchild，pre）； if（T->；RTag==Link）PostThreading（T->；rchild，pre）； if（!T->；lchild）{； T->；LTag=Thread；（）； }； if（pre &；&；!pre->；rchild）{； pre->；RTag=Thread； pre->；rchild=T； }； pre=T； }； return OK；}
A.T->lchild=pre
B.pre->lchild=T
C.T->rchild=pre
D.pre->rchild=T
正确答案：T->lchild=pre
8、1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。StatusExchangeBiTree（BiTree&； T）{； BiTree p； if（T）{； p=T->；lchild； T->；lchild=T->；rchild； T->；rchild=p； ExchangeBiTree（T->；lchild）；（）； }； return OK；}
A.ExchangeBiTree（p）；
B.ExchangeBiTree（T->rchild）
C.ExchangeBiTree（T->lchild->rchild）
D.ExchangeBiTree（T）
正确答案：ExchangeBiTree（T->rchild）
第七章单元测试
1、下图中结点B的出度为（）；
；
A.0
B.1
C.2
D.3
正确答案：1
2、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）
A.n ×n
B.（n-1）×（n-1）
C.（n-1）×n
D.n×（n+1）
正确答案：n ×n
3、采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
正确答案：层次遍历
4、下面的无向带权图的最小生成树包含的边有（）
A.ae ge gf eb bc cd
B.ae ed dc cb eg df
C.ag gf fd dc cb be
D.ae eb bc cd df eg
正确答案：ae ed dc cb eg df
5、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）
A.求关键路径的方法
B.求最短路径的Dijkstm方法
C.宽度优先遍历算法
D.深度优先遍历算法
正确答案：深度优先遍历算法
6、编写算法实现建立图的邻接表； StatusCreateAG（ALGraph &；G）{； int n，e，k，i，j； cout<；<；"请输入顶点数："； cin>；>；n； cout<；<；"请输入边数："； cin>；>；e； G.vernum=n； G.arcnum=e； // 建立顶点数组； for（k=0；k<；G.vernum；k++）{； cout<；<；"请输入顶点信息："； cin>；>；G.vertices[k].data； G.vertices[k].firstarc=NULL； }； // 建立邻接表； VertexType v1，v2； ArcNode *p，*q； for（k=0；k<；G.arcnum；k++）{； cout<；<；"请输入弧的始点和终点信息，中间用空格分开："； cin>；>；v1>；>；v2； i=LocateVex（G，v1）； if（i<；0|| i>；G.vernum-1） return ERROR； j=LocateVex（G，v2）； if（j<；0|| j>；G.vernum-1） return ERROR； if（i==j）return ERROR； p=newArcNode； if（!p）return ERROR； p->；adjvex=j； p->；nextarc=NULL； q=G.vertices[i].firstarc； if（!q）G.vertices[i].firstarc=p； else{； while（q->；nextarc）（）；// 指针定位于邻接表的尾结点； q->；nextarc=p； }； }； return OK；}
A.p=p->nextarc
B.q->nextarc=NULL
C.q->nextarc=p->nextarc
D.q=q->nextarc
正确答案：q=q->nextarc
7、编写算法实现从邻接表中取出某个顶点V的存储位置。intLocateVex（ALGraph&； G，VertexType v）{； int i=0； while（（）&；&；i<；G.vernum） i++； if（G.vertices[i].data==v） return i； else return -1；}
A.
A.G.vertices[i++].data!=v
B.G.vertices[i].data!=v
C.G.vertices[i].data==v
D.G.vertices[++i].data!=v
正确答案：G.vertices[i].data!=v
第八章单元测试
1、对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
正确答案：以顺序方式存储，且结点按关键字有序排序
2、下列描述中不符合二叉排序树特点的是（）
A.左子树中所有结点的关键字小于根结点的关键字
B.根结点的关键字大于左、右子树中所有结点的关键字
C.右字树中所有结点的关键字大于根节点的关键字C.
D.关键字插入的顺序影响二叉排序树的形态
正确答案：根结点的关键字大于左、右子树中所有结点的关键字
3、设哈希表长m=14，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4； addr（38）=5； addr（61）=6； addr（84）=7； 如用二次探测再散列处理冲突，关键字为49的结点的地址是（）
A.8
B.3
C.5
D.9
正确答案：9
4、试将折半查找的算法改写成递归算法。；Int； bisearch；（sqlist L，int low， int high；，elemtype x；）；{； If（low>；high）；return（0；）； else；{； if（L.data[mid]=；=x）；return；（mid）； else if；（L.data[mid]>；x）；bisearch（L，low，mid-1，x）； else； bisearch（L，mid+1，high，x）；} ；}//bisearch。
A.
A.mid<；（low+high）/2
B.mid=（low+high）/2
C.mid>（low+high）/2
D.mid!=（low+high）
正确答案：mid=（low+high）/2
5、设计算法判定给定二叉树是否为二叉排序树。；void BSTree（BiTree t，int &；flag，int &；last）；//声明Status IsBSTree（BiTree t）{； int flag = 1； int last =0； BSTree（t，flag，last）； return flag；}void BSTree（BiTree t，int &；flag，int &；last）//取地址不需要返回值{； if（t->；lchild&；&；flag） BSTree（t->；lchild，flag，last）；//遍历左子树； if（t->；data.key>；last&；&；flag）； last = t->；data.key；else flag=0；//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈keyif（t->；rchild&；&；flag）；}
A.BSTree（t->；rchild，flag，last）
B.BSTree（t->；lchild，flag，last）
C.BSTree（t->；rchild，last，flag）
D.BSTree（t->；lchild，last，flag）
正确答案：BSTree（t->；rchild，flag，last）
6、m阶B（）树中的m是指？
A.每个结点至少有m棵子树
B.每个结点至多有m棵子树
C.非终端结点中关键字的个数
D.m阶B（）树的深度（或高度）
正确答案：每个结点至多有m棵子树
第九章单元测试
1、设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（）。
A.40，50，20，95
B.15，40，60，20
C.15，20，40，45
D.45，40，15，20
正确答案：15，40，60，20
2、快速排序方法在情况下最不利于发挥其长处。（）
A.要排序的数据量太大。
B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序
D.要排序的数据个数为奇数
正确答案：要排序的数据已基本有序
3、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始推为（）。
A.79，46，56，38，40，80
B.84，79，56，38，40，46
C.84，79，56，46，40，38
D.84，56，79，40，46，38
正确答案：84，79，56，38，40，46
4、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，20，40，80，85，36，70
B.15，25，35，50，80，20，85，40，70，36
C.15，25，35，50，80，85，20，36，40，70
D.15，25，35，50，80，20，36，40，70，85
正确答案：15，25，35，50，20，40，80，85，36，70
5、试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<；MAXSIZE。void InsertionSort（SqList &；L ） { ； // 对顺序表 L 作直接插入排序。； for（i=k-1-1； i>；=1； --i ） ； {； if（L.r[i+1].key <； L.r[i].key）； { ； L.r[k+1] = L.r[i]； // 复制为监视哨for（j=i+1； L.r[k+1].key >； L.r[j].key； ++ j ）L.r[j-1] = L.r[j]；// 记录前移}//end if；}//end for； } // InsertSort
A.
A.L.r[j+1] = L.r[k+1]；
B.L.r[j] = L.r[k]
C.L.r[j] = L.r[k+1]；
D.L.r[i] = L.r[k+1]
正确答案：L.r[j] = L.r[k+1]；
6、1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：（1）采用顺序存储结构，至多使用一个记录的辅助存储空间；（2）算法的时间复杂度为O（n）；void Divide（int a（），int n）//把数组a中所有值为负的记录调到非负的记录之前
{low=0；high=n-1；while（）
{while（low<；high&；&；a[high]>；=0） high--； //以0作为虚拟的枢轴记录
a[low]<；->；a[high]；while（low<；high&；&；a[low]<；0） low++；a[low]<；->；a[high]；}
}//Divide
A.low<；=（high+1）
B.（low+1）<；high
C.low!=high
D.low<；high
正确答案：low<；high
第一章单元测试
1、图书馆的数目检索系统采用（）关系的数据结构。
A.集合
B.线性
C.树形
D.图状
正确答案：线性
2、（）是相互之间存在一种或多种特定关系的数据元素的集合。
A.数据
B.数据元素
C.数据项
D.数据结构
正确答案：数据结构
3、（）是一个值的集合和定义在这个值集上的一组操作的总称。
A.数据类型
B.数据元素
C.数据项
D.数据结构
正确答案：数据类型
4、算法的确定性是指（）
A.当输入数据非法时，算法也能作出反应或进行处理
B.在任何情况下，算法不会出现死循环
C.算法中的每一条指令必须有确切的含义
D.算法中没有逻辑错误
正确答案：算法中的每一条指令必须有确切的含义
第二章单元测试
1、线性表中的数据元素有一个前驱多个后继。
A.正确
B.错误
正确答案：错误
2、用顺序结构存储，删除最后一个结点时，（）
A.会移动其它结点位置
B.一定不会移动其它结点位置
C.可能会移动其它结点位置
D.其它
正确答案：一定不会移动其它结点位置
3、链表中逻辑上相邻的元素的物理地址（）相邻。
A.必定
B.不一定
C.一定不
D.其它
正确答案：不一定
4、1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose（）L（LinkList &；A，LinkList &；B，LinkList &；C）{； LinkList pa，pb，qa，qb； pa=A； pb=B； qa=pa； //保存pa的前驱指针； qb=pb； //保存pb的前驱指针； pa=pa->；next； pb=pb->；next； A->；next=NULL； C=A； while（pa&；&；pb）{； if（pa->；data<；pb->；data）{； qa=pa； pa=pa->；next； qa->；next=A->；next； //将当前最小结点插入A表表头； A->；next=qa； }； else{； qb=pb； pb=pb->；next；（）//将当前最小结点插入B表表头； A->；next=qb； }； }； while（pa）{； qa=pa； pa=pa->；next； qa->；next=A->；next； A->；next=qa； }； while（pb）{； qb=pb； pb=pb->；next； qb->；next=A->；next； A->；next=qb； }； pb=B； free（pb）； return OK；}
A.qa->next=A->next
B.qb->next=A->next
C.qa->next=A
D.qb->next=A
正确答案：qb->next=A->next
5、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。StatusListDelete（）CL（LinkList &；S）{； LinkList p，q； if（S==S->；next）return ERROR； q=S； p=S->；next； while（；）{； q=p； p=p->；next； }； q->；next=p->；next； free（p）； return OK；}
A.p->next!=S
B.p->next==S
C.p!=S
D.p==S
正确答案：p->next!=S
第三章单元测试
1、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（）
A.SXSSXXXX
B.SXXSXSSX
C.SXSXXSSX
D.SSSXXSXX
正确答案：SSSXXSXX
2、 设计一个迷宫求解的算法，采用（）数据结构最佳。
A.线性表的顺序存储结构
B.栈
C.队列
D.线性表的链式存储结构
正确答案：栈
3、循环队列存储在数组A[0..m-1]，则出队时的操作为（）
A.front=front+1
B.front=（front+1）mod（m-1）
C.front=（front+1）mod m
D.front=（front mod m）+1
正确答案：front=（front+1）mod m
4、1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&；序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&；’，且序列2是序列1的逆序列。例如，‘a+b&；b+a’是属该模式的字符序列，而‘1+3&；3-1’则不是。BOOLSymmetry（char a[]）{； int i=0； Stack s； InitStack（s）； ElemType x； while（a[i]!='&；' &；&； a[i]）{（）； i++； }； if（!a[i]） return FALSE； i++； while（a[i]）{； Pop（s，x）； if（x!=a[i]）{； DestroyStack（s）； return FALSE； }； i++； }； return TRUE；}
A.Pop（s，a[i++]）
B.Push（s，a[i++]）
C.Push（s，a[i]）
D.Pop（s，a[i]）
正确答案：Push（s，a[i]）
5、Status；SymmetryString（char*；p）{ Queue；q； if（!InitQueue（q））；return；0； Stack；s； InitStack（s）； ElemType；e1，e2； while（*p）{ Push（s，*p）； EnQueue（q，*p）； p++； } while（!StackEmpty（s））{ （）； DeQueue（q，e2）； if（e1!=e2）；return；FALSE； } return；OK；}
A.Pop（s，e1）
B.Push（s，*p）
C.EnQueue（q，*p）
D.P--P--P--P--P--P--P--P--
正确答案：Pop（s，e1）
第四章单元测试
1、设s=’I AM A STUDENT’ ， t=’GOOD’ ，则Concat（Substring（s，6，2），Concat（t，SubString（s，7，8）））=（）
A.A GOODWORKER
B.ST GOODSTUDENT
C.A GOOD STUDENT
D.A GOOD WORKER
正确答案：A GOOD STUDENT
2、空串与空格串是相同的，这种说法（）。
A.正确
B.不正确
正确答案：不正确
3、设串sl=″Data Structures with Java″，s2=“it″，则子串定位函数index（s1，s2）的值为（）。
A.15
B.16
C.17
D.18
正确答案：18
4、串的长度是指（）
A.串中所含不同字母的个数
B.串中所含字符的个数
C.串中所含不同字符的个数
D.串中所含非空格字符的个数
正确答案：串中所含字符的个数
5、串是一种数据对象和操作都特殊的线性表。
A.正确
B.错误
正确答案：正确
第五章单元测试
1、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
A.80
B.100
C.240
D.270
正确答案：240
2、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（）
A.1018
B.1024
C.1030
D.1072
正确答案：1072
3、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。
A.正确
B.错误
正确答案：错误
4、广义表（（），a，（（b，c），（），d），（（（e））））的长度为（）
A.3
B.4
C.5
D.2
正确答案：4
5、下面说法不正确的是（）。
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构
正确答案：广义表的表头总是一个广义表
6、1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。// 由广义表L复制广义表TintCopyGList（GList&； T，GList&； L）{； if（!L） T=NULL； else{； T=newGLNode； if（!T）exit（OVERFLOW）； T->；tag=L->；tag； if（L->；tag==ATOM）T->；atom=L->；atom； else{（）； CopyGList（T->；tp，L->；tp）； }； }； return OK；}
A.
A.CopyGList（T，L）
B.CopyGList（L->tp，T->tp）
C.CopyGList（L->hp，T->hp）
D.CopyGList（T->hp，L->hp）
正确答案：CopyGList（T->hp，L->hp）
第六章单元测试
1、已知一棵树边的集合为{<；I，M>；， <；I，N>；， <；E，I>；， <；B，E>；， <；B，D>；， <；A，B>；， <；G，J>；， <；G，K>；， <；C，G>；， <；C，F>；， <；H，L>；， <；C，H>；， <；A，C>；}，问这棵树中结点G的双亲结点为（）
A.A
B.C
C.I
D.B
正确答案：C
2、 一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为（）
A.9
B.10
C.11
D.12
正确答案：9
3、假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（）
A.结点A是结点D的双亲结点
B.结点A是结点D的右子树上的结点
C.结点A是结点D的左子树上的结点
D.结点A与结点D具有共同的双亲的右子树上的结点
正确答案：结点A是结点D的右子树上的结点
4、已知一棵树边的集合为{<；I，M>；， <；I，N>；， <；E，I>；， <；B，E>；， <；B，D>；， <；A，B>；， <；G，J>；， <；G，K>；， <；C，G>；， <；C，F>；， <；H，L>；， <；C，H>；， <；A，C>；}，将此树转化为二叉树后，E的左孩子为（）
A.A
B.C
C.I
D.B
正确答案：I
5、一棵哈夫曼树有17个结点，则其叶子结点的个数是（）。
A.7
B.8
C.9
D.10
正确答案：9
6、写递归算法，将二叉树中所有结点的左、右子树相互交换。Status ExchangeBiTree（BiTree&； T）{； BiTreep； if（T）{； p=T->；lchild； T->；lchild=T->；rchild； T->；rchild=p； ExchangeBiTree（T->；lchild）；（）；}； returnOK；}
A.
A.ExchangeBiTree（p）
B.ExchangeBiTree（T->rchild）
C.ExchangeBiTree（T->lchild->rchild）
D.ExchangeBiTree（T）
正确答案：ExchangeBiTree（T->rchild）
7、试写一个算法，为一棵二叉树建立后序线索二叉树。StatusPostOrderThreading（BiThrTree&； T，BiThrTree&； pre）；//首先建立后序线索树StatusFindNextInBiThrTree（BiThrTree&； q，TElemType *p）；//再进行查找；// 后序线索二叉树的算法StatusPostOrderThreading（BiThrTree&； Thrt，BiThrTree&； T）{； BiThrTree pre； Thrt=new BiThrNode； // 为线索二叉树建立头结点； if（!Thrt） exit（OVERFLOW）； Thrt->；LTag=Link； Thrt->；RTag=Thread； Thrt->；rchild=Thrt；// 右子树回指； if（!T） Thrt->；lchild=Thrt；// 若二叉树空，左子树回指； else{； Thrt->；lchild=T； pre=Thrt； PostThreading（T，pre）；// 后序遍历进行后序线索化； pre->；rchild=Thrt；//最后一个结点线索化； pre->；RTag=Thread； Thrt->；rchild=pre； }； return OK；}；StatusPostThreading（BiThrTree&； T，BiThrTree&； pre）{； if（T）{； if（T->；LTag==Link）PostThreading（T->；lchild，pre）； if（T->；RTag==Link）PostThreading（T->；rchild，pre）； if（!T->；lchild）{； T->；LTag=Thread；（）； }； if（pre &；&；!pre->；rchild）{； pre->；RTag=Thread； pre->；rchild=T； }； pre=T； }； return OK；}
A.T->lchild=pre
B.pre->lchild=T
C.T->rchild=pre
D.pre->rchild=T
正确答案：T->lchild=pre
8、1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。StatusExchangeBiTree（BiTree&； T）{； BiTree p； if（T）{； p=T->；lchild； T->；lchild=T->；rchild； T->；rchild=p； ExchangeBiTree（T->；lchild）；（）； }； return OK；}
A.ExchangeBiTree（p）；
B.ExchangeBiTree（T->rchild）
C.ExchangeBiTree（T->lchild->rchild）
D.ExchangeBiTree（T）
正确答案：ExchangeBiTree（T->rchild）
第七章单元测试
1、下图中结点B的出度为（）；
；
A.0
B.1
C.2
D.3
正确答案：1
2、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）
A.n ×n
B.（n-1）×（n-1）
C.（n-1）×n
D.n×（n+1）
正确答案：n ×n
3、采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
正确答案：层次遍历
4、下面的无向带权图的最小生成树包含的边有（）
A.ae ge gf eb bc cd
B.ae ed dc cb eg df
C.ag gf fd dc cb be
D.ae eb bc cd df eg
正确答案：ae ed dc cb eg df
5、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）
A.求关键路径的方法
B.求最短路径的Dijkstm方法
C.宽度优先遍历算法
D.深度优先遍历算法
正确答案：深度优先遍历算法
6、编写算法实现建立图的邻接表； StatusCreateAG（ALGraph &；G）{； int n，e，k，i，j； cout<；<；"请输入顶点数："； cin>；>；n； cout<；<；"请输入边数："； cin>；>；e； G.vernum=n； G.arcnum=e； // 建立顶点数组； for（k=0；k<；G.vernum；k++）{； cout<；<；"请输入顶点信息："； cin>；>；G.vertices[k].data； G.vertices[k].firstarc=NULL； }； // 建立邻接表； VertexType v1，v2； ArcNode *p，*q； for（k=0；k<；G.arcnum；k++）{； cout<；<；"请输入弧的始点和终点信息，中间用空格分开："； cin>；>；v1>；>；v2； i=LocateVex（G，v1）； if（i<；0|| i>；G.vernum-1） return ERROR； j=LocateVex（G，v2）； if（j<；0|| j>；G.vernum-1） return ERROR； if（i==j）return ERROR； p=newArcNode； if（!p）return ERROR； p->；adjvex=j； p->；nextarc=NULL； q=G.vertices[i].firstarc； if（!q）G.vertices[i].firstarc=p； else{； while（q->；nextarc）（）；// 指针定位于邻接表的尾结点； q->；nextarc=p； }； }； return OK；}
A.p=p->nextarc
B.q->nextarc=NULL
C.q->nextarc=p->nextarc
D.q=q->nextarc
正确答案：q=q->nextarc
7、编写算法实现从邻接表中取出某个顶点V的存储位置。intLocateVex（ALGraph&； G，VertexType v）{； int i=0； while（（）&；&；i<；G.vernum） i++； if（G.vertices[i].data==v） return i； else return -1；}
A.
A.G.vertices[i++].data!=v
B.G.vertices[i].data!=v
C.G.vertices[i].data==v
D.G.vertices[++i].data!=v
正确答案：G.vertices[i].data!=v
第八章单元测试
1、对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
正确答案：以顺序方式存储，且结点按关键字有序排序
2、下列描述中不符合二叉排序树特点的是（）
A.左子树中所有结点的关键字小于根结点的关键字
B.根结点的关键字大于左、右子树中所有结点的关键字
C.右字树中所有结点的关键字大于根节点的关键字C.
D.关键字插入的顺序影响二叉排序树的形态
正确答案：根结点的关键字大于左、右子树中所有结点的关键字
3、设哈希表长m=14，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4； addr（38）=5； addr（61）=6； addr（84）=7； 如用二次探测再散列处理冲突，关键字为49的结点的地址是（）
A.8
B.3
C.5
D.9
正确答案：9
4、试将折半查找的算法改写成递归算法。；Int； bisearch；（sqlist L，int low， int high；，elemtype x；）；{； If（low>；high）；return（0；）； else；{； if（L.data[mid]=；=x）；return；（mid）； else if；（L.data[mid]>；x）；bisearch（L，low，mid-1，x）； else； bisearch（L，mid+1，high，x）；} ；}//bisearch。
A.
A.mid<；（low+high）/2
B.mid=（low+high）/2
C.mid>（low+high）/2
D.mid!=（low+high）
正确答案：mid=（low+high）/2
5、设计算法判定给定二叉树是否为二叉排序树。；void BSTree（BiTree t，int &；flag，int &；last）；//声明Status IsBSTree（BiTree t）{； int flag = 1； int last =0； BSTree（t，flag，last）； return flag；}void BSTree（BiTree t，int &；flag，int &；last）//取地址不需要返回值{； if（t->；lchild&；&；flag） BSTree（t->；lchild，flag，last）；//遍历左子树； if（t->；data.key>；last&；&；flag）； last = t->；data.key；else flag=0；//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈keyif（t->；rchild&；&；flag）；}
A.BSTree（t->；rchild，flag，last）
B.BSTree（t->；lchild，flag，last）
C.BSTree（t->；rchild，last，flag）
D.BSTree（t->；lchild，last，flag）
正确答案：BSTree（t->；rchild，flag，last）
6、m阶B（）树中的m是指？
A.每个结点至少有m棵子树
B.每个结点至多有m棵子树
C.非终端结点中关键字的个数
D.m阶B（）树的深度（或高度）
正确答案：每个结点至多有m棵子树
第九章单元测试
1、设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（）。
A.40，50，20，95
B.15，40，60，20
C.15，20，40，45
D.45，40，15，20
正确答案：15，40，60，20
2、快速排序方法在情况下最不利于发挥其长处。（）
A.要排序的数据量太大。
B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序
D.要排序的数据个数为奇数
正确答案：要排序的数据已基本有序
3、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始推为（）。
A.79，46，56，38，40，80
B.84，79，56，38，40，46
C.84，79，56，46，40，38
D.84，56，79，40，46，38
正确答案：84，79，56，38，40，46
4、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，20，40，80，85，36，70
B.15，25，35，50，80，20，85，40，70，36
C.15，25，35，50，80，85，20，36，40，70
D.15，25，35，50，80，20，36，40，70，85
正确答案：15，25，35，50，20，40，80，85，36，70
5、试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<；MAXSIZE。void InsertionSort（SqList &；L ） { ； // 对顺序表 L 作直接插入排序。； for（i=k-1-1； i>；=1； --i ） ； {； if（L.r[i+1].key <； L.r[i].key）； { ； L.r[k+1] = L.r[i]； // 复制为监视哨for（j=i+1； L.r[k+1].key >； L.r[j].key； ++ j ）L.r[j-1] = L.r[j]；// 记录前移}//end if；}//end for； } // InsertSort
A.
A.L.r[j+1] = L.r[k+1]；
B.L.r[j] = L.r[k]
C.L.r[j] = L.r[k+1]；
D.L.r[i] = L.r[k+1]
正确答案：L.r[j] = L.r[k+1]；
6、1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：（1）采用顺序存储结构，至多使用一个记录的辅助存储空间；（2）算法的时间复杂度为O（n）；void Divide（int a（），int n）//把数组a中所有值为负的记录调到非负的记录之前
{low=0；high=n-1；while（）
{while（low<；high&；&；a[high]>；=0） high--； //以0作为虚拟的枢轴记录
a[low]<；->；a[high]；while（low<；high&；&；a[low]<；0） low++；a[low]<；->；a[high]；}
}//Divide
A.low<；=（high+1）
B.（low+1）<；high
C.low!=high
D.low<；high
正确答案：low<；high