《数据结构试题8》由会员分享，可在线阅读，更多相关《数据结构试题8（48页珍藏版）》请在金锄头文库上搜索。
1、数据结构试题一、 单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（D）A 必须是连续的B部分地址必须是连续的C 一定是不连续的D可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（D ）。AnBn/2C(n-1)/2D(n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D）。Aslink =plink;plink=s;Bplink =s;slink = q;Cpl
2、ink =slink; slink=p;Dqlink =s;slink = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。A起泡排序 B堆排序 C锦标赛排序D快速排序6、 设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）。A 求子串 B模式匹配 C 串替换D串连接7、在数组A中，每一个数组元素Aij占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（C ）。A 80B 100 C 240D 2708、 将一个递归算法改为对应的非递归算法时，通常需要使用（A ）。A
3、栈 B队列 C循环队列D优先队列9、 一个队列的进队列顺序是1, 2, 3, 4,则出队列顺序为（C ）。10、在循环队列中用数组A0.m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（D ）。A( front - rear + 1) % mC( front - rear + m) % m11、 一个数组元素ai与(AA * (a+i) B a+i12、若需要利用形参直接访问实参A指针B引用13、下面程序段的时间复杂度为(for (int i=0;im;i+)for (int j=0;jlink=p;p-link=s;B s-link=p-link;p-
4、link=s;C s-link=p-link;p=s;D p-link=s;s-link=p;19、设单链表中结点结构为（data,link）.已知指针q所指结点是指针p所指结点的直接前驱，若在*4与*?之间插入结点*s，则应执行下列哪一个操作（B ）A s-link=p-link; p-link=s; B q-link=s; s-link=pC p-link=s-link; s-link=p; D p-link=s; s-link=q;20、设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继，则应执行下列哪一个操作（A ）A p-link=p-link-link;B p=
5、p-link; p-link=p-link-link;C p-link=p-link;D p=p-link-link;21、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头 结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪 一个操作（D ）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; s
6、 为第一个结点硫22、设单循环链表中结点的结构为（data,link），且first为指向链表表头的指 针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的 语句是（D ）。A current-link =null B first-link=currentC first=currentD current-link=first？ 23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是（C ）。A c,b,a B b,a,cC c,a,bD a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是（A ）。A top=0 B top=maxSize C top
7、=maxSize D top=-125、栈和队列的共同特点是（C ）。A 都是先进后出B都是先进先出C只允许在端点处插入和删除D没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判断队空 的条件为（D ）.A f+1= =rB r+1= =fC f= =0D f= =r27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）A n-2B n-1 C nD n+128、当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A top+;B top-;C top=0; D top;29、设链
8、式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想 摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（A ） 操作。A x=top-data; top=top-link;B top=top-link; x=top-data;C x=top; top=top-link;D x=top-data;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct （Data Type dataMaxsize;Int front, rear; Queue;若有一个Queue类型的队列Q
9、，试问判断队列满的条件应是下列哪一个语句（D ）A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;C Q.front + Q.rear= = Maxsize;D Q.front=(Q.rear+1)% Maxsize;31、设有一个递归算法如下: int fact (int n )( if (n=0) return 1;else return n*fact(n-1);下面正确的叙述是(B )A计算fact(n)需要执行n次递归B fact(7)=5040C此递归算法最多只能计算到fact(8)D以上结论都不对32、设有一个递归算法如下int x
10、 (int n) (if (n=3) return 1;else return x(n-2)+x(n-4)+1;试问计算x(x(8)时需要计算(D)次x函数。A 8次B 9 次 C 16 次D 18次33、 设有广义表D(a,b,D),其长度为(B)，深度为(A )A 8B 3C 2D 534、广义表A(a),则表尾为(C )B ()C 空表D(a)35、下列广义表是线性表的有(C )A E (a,(b,c)B E(a,E)C E (a,b) DE(a,L()36、递归表、再入表、纯表、线性表之间的关系为(C )A再入表 递归表纯表线性表B递归表线性表 再入表纯表C递归表再入表纯表线性表D递归
11、表再入表线性表纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是(B )的二叉 树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为气，度为2的结点为n2.,则(A )A n n +1 B n = n +1 C n 2n +1D n =2n +10=2200=22039、由权值分别为11，8, 6, 2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为(B)A 24B 73C 48D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I个结点的地址为(A )。A da
12、1+(I-1)*mB da1+I*mC da1-I*m D da1+(I+1)*m41、34具有35个结点的完全二叉树的深度为(A )A 5 B 6 C 7 D 842、对线性表进行折半搜索时，要求线性表必须(C )A以链接方式存储且结点按关键码有序排列B以数组方式存储C以数组方式存储且结点按关键码有序排列D以链接方式存储43、顺序搜索算法适合于存储结构为（B ）的线性表。A散列存储B顺序存储或链接存储C压缩存储D索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C ）A O （n2）B O （n log2n）C O （log2n）D O （n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为（A ）A nB n+1C n-1 D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C）。A求关键路径的方法B求最短路径的Dijkstra方法C深度优先遍历算法D广度优先遍历算法47、 在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为（A ）A 1B 2C 9D 1048、对包含n个元素的散列表进行搜索，平均搜索长度为（C ）A O（log2n）B O（n） C不直接依赖于nD 上述都
