河南理工大学数据结构_联大系统成人高考函授考试答案

答案是：void QkSort(rectype r[],int n) { // r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储， //本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。 int i=1,j=1,k=n,temp; while (k!=j){ while (r[k].key==3) k--;// 当前元素是兰色砾石，指针左移 if (r[k].key==1) // 当前元素是红色砾石 if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;} //左侧只有红色砾石，交换r[k]和r[i] else {temp=r[j];r[j]=r[i];r[i]=temp; j++; //左侧已有红色和白色砾石，先交换白色砾石到位 temp=r[k];r[k]=r[i];r[i]=temp; i++; //白色砾石（i所指）和待定砾石（j所指） } //再交换r[k]和r[i]，使红色砾石入位。 if (r[k].key==2) if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;} // 左侧已有白色砾石，交换r[k]和r[j] else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;} //i、j分别指向红、白色砾石的后一位置 }//while if (r[k]==2) j++; /* 处理最后一粒砾石 else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; } //最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1 }//结束QkSor算法

有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。

答案是：typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下 temp->next=p; p->prior->next=temp; //将temp插到p结点前 temp->prior=p->prior; p->prior=temp; } else p=p->next; //无交换，指针后移 tail=p; //准备向上起泡 p=tail->prior; while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小元素冒出 if (p->dataprior->data) //交换两结点指针，涉及6条链 {temp=p->prior; exchange=1; //有交换 p->prior=temp->prior;temp->prior->next=p； //先将temp结点从链表上摘下 temp->prior=p; p->next->prior=temp; //将temp插到p结点后（右） temp->next=p->next; p->next=temp; } else p=p->prior; //无交换，指针前移 head=p; //准备向下起泡 }// while (exchange) } //算法结束

试以单链表为存储结构，实现简单选择排序算法

答案是：void LinkedListSelectSort(LinkedList head) //本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下 //当前结点和最小结点的前驱指针 p=head->next; while(p!=null) {q=p->next; r=p; //设r是指向关键字最小的结点的指针 while (q!=null) {if(q->datadata) r=q; q:=q->next; } if(r!=p) r->data<-->p->data; p=p->next; }

对22个记录的有序表作折半查找，查找失败时，至少需要比较___个关键字。

答案是： 4

m阶B-树的非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树。 A.正确 B.错误

答案是：参考答案：对

分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。

答案是：bool insert(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while (p->next){ if(p->next->data==data) return false; p=p->next; } //找到插入位置 LinkList s; s=new LNode; s->data=data; s->next=p->next; p->next=s; //插入该结点 return true; } bool deletes(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while (p->next){ if(p->next->data==data){ LinkList s=p->next; p->next=s->next; delete s; //删除该结点 return true; } //找到删除位置 p=p->next； //遍历下一个结点 } return false; }

假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。

答案是：int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p） {level++； // 树的高度增1 if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下 //bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义 else p=p->lchild； //bf>=0 沿左分枝向下 }//while return （level）；//平衡二叉树的高度 } //算法结束

已知二叉树T的结点形式为（lling,data,count,rlink），在树中查找值为X的结点，若找到，则记数（count）加1，否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

答案是：void SearchBST(BiTree &T,int target){ BiTree s,q,f; //以数据值target,新建结点s s=new BiTNode; s->data.x=target; s->data.count=0; s->lchild=s->rchild=NULL; if(!T){ T=s; return ; } //如果该树为空则跳出该函数 f=NULL; q=T; while (q){ if (q->data.x==target){ q->data.count++; return ; } //如果找到该值则计数加一 f=q; if (q->data.x>target) //如果查找值比目标值大，则为该树左孩子 q=q->lchild; else //否则为右孩子 q=q->rchild; } //将新结点插入树中 if(f->data.x>target) f->lchild=s; else f->rchild=s; }

已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild，rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树

答案是：void Print（BSTree t） // 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； Coutdatarchild；//沿右分枝找第一个值≥x的结点 bst=p; //bst所指结点是值≥x的结点的树的根 if（p） {f=p; p=p->lchild ；//找第一个值data≥x）//沿左分枝向下，找第一个值lchild ；} //f是p的双亲结点的指针，指向第一个值≥x的结点 if(p) f->lchild=null; //双亲与找到的第一个值

试写一个判别给定二叉树是否为二叉排序树的算法。

答案是：#define true 1 #define false 0 typedef struct node {datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBST（BTree T,int flag） // 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（T!=null && flag） { Judgebst（T->lchild,flag）；// 中序遍历左子树 if（pre==null）pre=T；// 中序遍历的第一个结点不必判断 else if（pre->datadata）pre=T；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （T->rchild,flag）；// 中序遍历右子树 }//JudgeBST算法结束

试写出折半查找的递归算法。

答案是：int BinSrch（rectype r[ ]，int k，low，high） //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; } else return （0）；//查找失败。 }//算法结束

设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。

答案是： m=2e

对连通图进行深度优先遍历可以访问到该图中的所有顶点。 A.正确 B.错误

答案是：参考答案：对

采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。

答案是：int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k) //判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) {l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len

试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

答案是：int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist_path_DFS

设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。

答案是：int ShortestPath_MAX(AMGraph G, int v0){ //用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点m n=G.vexnum; //n为G中顶点的个数 for(v = 0; v

一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

答案是：Void DFSn(Graph G,int v) { //从第v个顶点出发非递归实现深度优先遍历图G Stack s; SetEmpty(s); Push(s,v); While(!StackEmpty(s)) { //栈空时第v个顶点所在的连通分量已遍历完 Pop(s,k); If(!visited[k]) { visited[k]=TRUE; VisitFunc(k); //访问第k个顶点 //将第k个顶点的所有邻接点进栈 for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w)) { if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s) } } }

分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ① 增加一个新顶点v，InsertVex(G, v)； ② 删除顶点v及其相关的边，DeleteVex(G, v); ③ 增加一条边，InsertArc(G, v, w); ④ 删

答案是：假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下： ① 增加一个新顶点v Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex ② 删除顶点v及其相关的边， Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[j].adj) { G.arcs[j].adj=1; G.arcnum++; } return OK; }//Insert_Arc ④ 删除一条边 Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[j].adj) { G.arcs[j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。 Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=new ArcNode; p->adjvex=j;p->nextarc=NULL; if(!G.vertices.firstarc) G.vertices.firstarc=p; else { for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc

设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的先序遍历序列为____________________。

答案是：CBDA

由树转化成二叉树，该二叉树的右子树不一定为空。 A.正确 B.错误

答案是：参考答案：错

输出二叉树中从每个叶子结点到根结点的路径。

答案是：void AllPath(BTNode *b,ElemType path[],int pathlen) {int i; if (b!=NULL) {if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点 {cout << " " << b->data << "到根结点路径:" << b->data; for (i=pathlen-1;i>=0;i--) cout << endl; } else {path[pathlen]=b->data; //将当前结点放入路径中 pathlen++; //路径长度增1 AllPath(b->lchild,path,pathlen); //递归扫描左子树 AllPath(b->rchild,path,pathlen); //递归扫描右子树 pathlen--; //恢复环境 } }// if (b!=NULL) }//算法结束

求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

答案是：void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0) {while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到l栈，记住最高栈顶指针，退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath

用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。

答案是：int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {p=QueueOut(Q); coutlchild && !p->rchild ||!p->lchild && p->rchild)num++; //度为1的结点 if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } // while(!QueueEmpty(Q)) }//if(bt) return(num); }//返回度为1的结点的个数

计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

答案是：int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else {BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1; //front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last) {p=Q[front++]; temp++; //同层元素数加1 if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear; if(temp>maxw) maxw=temp; //last指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while return (maxw); }//结束width

设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。

答案是：void DoubleTraverse(BiTree T) { if(T == NULL) return; else if(T->lchild==NULL&&T->rchild==NULL) coutlchild); //递归遍历左子树 coutrchild); //递归遍历右子树 } }

交换二叉树每个结点的左孩子和右孩子。

答案是：void ChangeLR(BiTree &T) { BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; }//交换左右孩子 ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树 }

判别两棵树是否相等。

答案是：int compareTree(TreeNode* tree1, TreeNode* tree2) //用分治的方法做，比较当前根，然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {//如果两个都是NULL，则相等 return 0; }//如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 if(tree1->c != tree2->c) { 　return 1; } return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right)) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); }//算法结束

以二叉链表作为二叉树的存储结构，编写以下算法：（1）统计二叉树的叶结点个数。

答案是：int LeafNodeCount(BiTree T) { if(T==NULL) return 0; //如果是空树，则叶子结点个数为0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); }

试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同

答案是：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则有 ① 或为空树，或为只有根结点的二叉树 ② 或为空树，或为任一结点至多只有左子树的二叉树． ③ 或为空树，或为任一结点至多只有右子树的二叉树． ④ 或为空树，或为任一结点至多只有右子树的二叉树

二维数组S，行下标i从0到7，列下标j从0 到9，每个元素占3个字节，若从首地址S开始以列序为主序将元素连续存放在存储器内，则元素S [4][7]的起始地址为。

答案是： S+180

串是元素类型为字符型的线性表。 A.正确 B.错误

答案是：参考答案：对

设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0(n)）。

答案是：void Arrange(int A[],int n) //n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 {int i=0,j=n-1,x; //用类C编写，数组下标从0开始 while(i0) i++; while(i

设二维数组a[1..m, 1..n] 含有m*n 个整数。 ① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)； ② 试分析算法的时间复杂度。

答案是：int JudgEqual(ing a[m][n],int m,n) //判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。 {for(i=0;i

已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。

答案是：void format (char *s1,*s2,*s3) //将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐 {char *p=s1, *q=s2; int i=0; while(*p!= '\0' && *p== ' ') p++;//滤掉s1左端空格 if(*p== '\0') {cout<<"字符串s1为空串或空格串"<

编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

答案是：void insert(char *s,char *t,int pos) //将字符串t插入字符串s的第pos个位置。 {int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针 if(pos<1) {cout<<“pos参数位置非法”<=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上

写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

答案是：void InvertStore(char A[]) //字符串逆序存储的递归算法。 {char ch; static int i = 0;//需要使用静态变量 cin>>ch; if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A); A[i++] = ch;//字符串逆序存储 } A[i] = '\0'; //字符串结尾标记 }

写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。

答案是：void Count（） //统计输入字符串中数字字符和字母字符的个数。｛int i，num[36]； char ch；　for（i＝0；i<36；i++）num[i]＝０；// 初始化　while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。　　　if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符　　 else　if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符　for（i=0；i<10；i++） // 输出数字字符的个数 cout<<“数字”<

请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear)

答案是： H（H（T（H（T（H（T（L）））））））

数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存

答案是：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142

设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

答案是： ① p的nextval函数值为0110132。（p的next函数值为0111232）。 ② 利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)

已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

答案是：模式串t的next和nextval值如下： j 1 2 3 4 5 6 7 8 9 10 11 12 t串 a b c a a b b a b c a b next[j] 0 1 1 1 2 2 3 1 2 3 4 5 nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

答案是：对

最大容量为n的循环队列，队尾指针是rear，队头是front，若牺牲一个空间不用，则队列满的条件是____________________。

答案是：(rear+1)%n==front

已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。

答案是：① int GetMax(LinkList p) { if(!p->next) return p->data; else { int max=GetMax(p->next); return p->data>=max ? p->data:max; } } ② int GetLength(LinkList p) { if(!p->next) return 1; else { return GetLength(p->next)+1; } } ③ double GetAverage(LinkList p , int n) { if(!p->next) return p->data; else { double ave=GetAverage(p->next,n-1); return (ave*(n-1)+p->data)/n; } }

如果允许在循环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出“从队尾删除”和“从队头插入”的算法。

答案是：① #define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ② elemtp delqueue ( cycqueue Q) //Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。 {if (Q.front==Q.rear) { cout<<"队列空"<

假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(

答案是：(1)初始化 SeQueue QueueInit(SeQueue Q) {//初始化队列 Q.front=Q.rear=0; Q.tag=0; return Q; } (2)入队 SeQueue QueueIn(SeQueue Q,int e) {//入队列 if((Q.tag==1) && (Q.rear==Q.front)) cout<<"队列已满"<

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。

答案是：typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针 (1) 置空队 void InitQueue( LinkQueue *Q) { //置空队：就是使头结点成为队尾元素　QueueNode *s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; delete s; 　}//回收结点空间 } (2) 判队空 int EmptyQueue( LinkQueue *Q) { //判队空。当头结点的next指针指向自己时为空队　return Q->rear->next->next==Q->rear->next; } (3) 入队 void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *p=new QueueNode;//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } (4) 出队 Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error("Queue underflow"); p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点　Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p delete p;//释放被删结点 return x; }

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C.

答案是：①A和D是合法序列，B和C 是非法序列。 ②设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){cout<<“序列非法”<

从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。

答案是：float expr( ) //从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。 cin>>x;//x是字符型变量。 while(x!=’$’) {switch {case‘0’<=x<=’9’: while((x>=’0’&&x<=’9’)||x==’.’) //拼数 if(x!=’.’) //处理整数 {num=num*10+（ord(x)-ord(‘0’)）; cin>>x;} else //处理小数部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; cin>>x; } }//else push(OPND,num); num=0.0;//数压入栈，下个数初始化 case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break; case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break; case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch cin>>x;//读入表达式中下一个字符。 }//结束while（x！=‘$’） cout<<“后缀表达式的值为”<

设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

答案是：#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {cin>>x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。｛if(top==maxsize-1){cout<<“栈满”<

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

答案是：#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量长度 for ( i=0; i

将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进

答案是：(1) 栈初始化 int Init() {S.top[0]=-1; S.top[1]=m; return 1; //初始化成功 } (2) 入栈操作： int push(stk S ,int i,int x) ∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0 {if(i<0||i>1){ cout<<“栈号输入不对”<1){cout<<“栈号输入错误”<

系统软件通常由____、____、____和____等组成。

答案是：操作系统、语言处理程序、数据库管理程序、服务程序

算机安全是指计算机财产的安全。计算机财产包括____和____。

答案是：系统资源、信息资源

非空的线性结构中，有且仅有一个元素没有直接前驱。

答案是：对

下面是删除带头结点的单链表中首元结点的程序片段，Ｌ为头指针，则应在空的位置填上　　　。p=L->next;if(p) { L->next= ; free(p);}

答案是： p->next

已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

答案是：void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i

已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。

答案是：void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换 p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱 }∥算法exchange结束。

设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

答案是：void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->datanext; // 查找第一个值 ≥maxk的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 }//if }

设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

答案是：void inverse(LinkList &L) {// 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } }

设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

答案是： ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，则重新赋值 p=p->next;//遍历链表 } return pmax->data;

设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

答案是： void DisCompose(LinkedList A) { B=A; B->next= NULL; ∥B表初始化 C=new LNode;∥为C申请结点空间 C->next=NULL; ∥C初始化为空表 p=A->next; ∥p为工作指针 while(p!= NULL) { r=p->next; ∥暂存p的后继 if(p->data<0) {p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法 else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法 p=r;∥p指向新的待处理结点。 } }

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

答案是： void Difference（LinkList& La, LinkList& Lb,int *n） {∥差集的结果存储于单链表La中，*n是结果集合中元素个数，调用时为0 pa=La->next; pb=Lb->next; ∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 pre=La; ∥pre为La中pa所指结点的前驱结点的指针 while（pa&&pb） {if（pa->datadata）{pre=pa;pa=pa->next;*n++;} ∥ A链表中当前结点指针后移 else if（pa->data>q->data）q=q->next; ∥B链表中当前结点指针后移 else {pre->next=pa->next; ∥处理A，B中元素值相同的结点，应删除 u=pa; pa=pa->next; delete u;} ∥删除结点 } }

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。

答案是： void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) { pa=La->next;pb=Lb->next; pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) { if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->datadata) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;} } while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间 pc->next=null;∥置链表尾标记。 delete Lb; //释放Lb的头结点 }

将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

答案是：oid MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next=NULL; while(pa||pb ) {//只要存在一个非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表为空，用q指向pb，pb指针后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表为空，用q指向pa，pa指针后移 else if(pa->data<=pb->data) {q=pa; pa=pa->next;} //取较小者（包括相等）La中的元素，用q指向pa，pa指针后移 else {q=pb; pb=pb->next;} //取较小者Lb中的元素，用q指向pb，pb指针后移 q->next = Lc->next; Lc->next = q; //将q指向的结点插在Lc 表的表头结点之后 } delete Lb; //释放Lb的头结点 }

将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

答案是： void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) {if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;} //取较小者La中的元素，将pa链接在pc的后面，pa指针后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移 else //相等时取La中的元素，删除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点 }

下面程序段的时间复杂度是（）。x=0;for(i=1;i<=n;i=2*i) for(j=1;j<=n;j++) x++;

答案是： O(nlog2n)

数据结构是相互之间存在一种或多种特定关系的（）的集合。

答案是：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

存储结构

答案是：数据对象在计算机中的存储表示，也称为物理结构。

数据对象

答案是：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据项

答案是：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据元素

答案是：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

线性表的顺序存储结构比链式存储结构更好。 A.正确 B.错误

答案是：参考答案：错

为什么计算机内一定要配置端口或接口？

答案是： I/O设备一般不和微机内部直接相连，而是必须通过I/O接口与微机内部进行信息交换。首先，微机和I/O设备两者的信息类型和格式可能不一样。外设种类繁多，信号类型十分复杂，它既可以是机械式的、电动式的或电子式的，也可以是其他形式的；所使用的信号可以是数字量或模拟量，也可以是开关量；即使是数字量，也可能与微机在信号线的功能定义、逻辑定义上都不一致；必须通过I/O接口实现微机与外部设备的隔离和信号转换。其次，微机和I/O设备信号传输处理的速度往往不匹配，信号时序有很大差别，必须通过I/O接口来进行缓冲和协调。再次，随着计算机技术的发展，I/O设备的种类日益丰富，一台多媒体微机可能要配置数十个I/O设备，若不通过接口，而由CPU直接对I/O设备的操作实施控制，就会使CPU一直忙于与外设打交道，大大降低CPU的效率。最后，若I/O设备直接由CPU控制，也会使外设的硬件结构依赖于CPU，对外设本身的发展不利。I/O接口的引入，使得CPU对I/O设备的操作转化为对I/O接口的操作。可见，I/O接口是微机与外部设备之间进行信息交换的中转站，是任何微机应用系统必不可少的重要组成部分。

存储结构由哪两种基本的存储方法实现？

答案是：1）顺序存储结构，顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构，顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案是：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。

试分析下面各程序段的时间复杂度。x=0; for(i=1; i

答案是：O(n2)

试分析下面各程序段的时间复杂度。i=1; while(i<=n) i=i*3;

答案是： O(log3n)

试分析下面各程序段的时间复杂度。s=0; for i=0; i

答案是： O(n2)

试分析下面各程序段的时间复杂度。for (i=0; i

答案是： O(m*n)

试分析下面各程序段的时间复杂度。（1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++;

答案是： O(1)

下列排序方法中，（　）是稳定的排序方法。 A..希尔排序 B..冒泡排序 C..快速排序 D.归并排序

答案是：参考答案：BD

快速排序在最坏情况下的时间复杂度为（）。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2)

答案是：参考答案：D

从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 A.归并排序 B.冒泡排序 C.插入排序 D.选择排序

答案是：参考答案：D

对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。 A.从小到大排列好的 B.从大到小排列好的 C.元素无序 D.元素基本有序

答案是：参考答案：B

对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。 A.n+1 B.n C.n-1 D.n(n-1)/2

答案是：参考答案：D

快速排序在下列（）情况下最易发挥其长处。 A.被排序的数据中含有多个相同排序码 B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中的最大值和最小值相差悬殊

答案是：参考答案：C

对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。 A.O(n) B.O(n2) C.O(nlog2n) D.O(n3)

答案是：参考答案：B

若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。 A.38，40，46，56，79，84 B.40，38，46，79，56，84 C.40，38，46，

答案是：参考答案：C

下列关键字序列中，（）是堆。 A.16，72，31，23，94，53 B.94，23，31，72，16，53 C.16，53，23，94，31，72 D.16，23，53，31，94，72

答案是：参考答案：D

堆是一种（）排序。 A.插入 B.选择 C.交换 D.归并

答案是：参考答案：B

堆的形状是一棵（）。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树

答案是：参考答案：C

若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。 A.79，46，56，38，40，84 B.84，79，56，38，40，46 C.84，79，56，46，40，38 D.84，

答案是：参考答案：B

下述几种排序方法中，要求内存最大的是（）。 A.希尔排序 B.快速排序 C.归并排序 D.堆排序

答案是：参考答案：C

下述几种排序方法中，（）是稳定的排序方法。 A.希尔排序 B.快速排序 C.归并排序 D.堆排序

答案是：参考答案：C

数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。 A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序

答案是：参考答案：D

下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.希尔排序 B.快速排序 C.冒泡排序 D.堆排序

答案是：参考答案：A

从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。 A.归并排序 B.冒泡排序 C.插入排序 D.选择排序

答案是：参考答案：C

下面关于B-和B+树的叙述中，不正确的是（）。 A.．B-树和B+树都是不平衡的多叉树 B.B-树和B+树都可用于文件的索引结构 C.B-树和B+树都能有效地支持顺序检索 D.B-树和B+树都能有效地支持随机检索

答案是：参考答案：AC

采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。 A.不一定都是同义词 B.一定都是同义词 C.一定都不是同义词 D.都相同

答案是：参考答案：A

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n

答案是：参考答案：C

适用于折半查找的表的存储方式及元素排列要求为（）。 A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序

答案是：参考答案：D

如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。 A.顺序查找 B.折半查找 C.分块查找 D.哈希查找

答案是：参考答案：C

折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。 A.20，70，30，50 B.30，88，70，50 C.20，50 D.30，88

答案是：参考答案：A

对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。 A.3 B.4 C.5 D.6

答案是：参考答案：B

目前为： 1/2 页首页上页下页尾页