数据结构考试及答案（）作者:日期: 2数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D）A 必须是连续的B部分地址必须是连续的C 一定是不连续的D可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（D ）。
An B n/2 C （n-1）/2 D （n+1）/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）oA s—link = p—link ；p—link = s；B p—link = s; s—link = q;C p—link = s—link ；s—link = p；D q—link = s; s—link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。
A 起泡排序B 堆排序C锦标赛排序 D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）oA 求子串B模式匹配C 串替换 D 串连接7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8,列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B队列C循环队列D优先队列9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。
10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A （ front - rear + 1） % mB （rear - front + 1） %mC （ front - rear + m） % mD （ rear - front + n） % m11、一个数组元素a[i]与（A ）的表示等价。
A * （a+i）B a+iC *a+iD &a+i12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数A指针 B 引用C值 D 变量13、下面程序段的时间复杂度为（C)for (i nt i=0;i<m;i++)for (i nt j=0;j <n ;j++)a[i][j]=i*j；A O(m2)B O(n 2)C O(m* n)D O(m+n)14、下面程序段的时间复杂度为（B)int f(un sig ned int n) {if(n= =0 || n= =1) retur n 1;else return n*f(n -1);}A 0（1）B 0（n）C O（n 2）D O（n !）15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（D） A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续或不连续都可以16、数据结构的定义为（D，S），其中D是（B ）的集合。
A算法B数据元素 C 数据操作 D 逻辑结构17、算法分析的目的是（A ）。
A 找出数据结构的合理性B 研究算法中输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点, 则执行（B ）。
A s->li nk=p;p->li nk=s;B s->li nk=p->li nk;p->li nk=s;C s->li nk=p->li nk;p=s;D p->li nk=s;s->li nk=p;19、设单链表中结点结构为（data,link）. 已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（B ）A s->li nk=p->li nk; p->li nk=s;B q->li nk=s; s->li nk=pC p->li nk=s->li nk; s->li nk=p;D p->li nk=s; s->li nk=q;20、设单链表中结点结构为（data,link）. 若想摘除结点*p的直接后继，则应执行下列哪一个操作（A ）A p->li nk=p->li nk->li nk;B p=p->li nk; p->li nk=p->li nk->li nk;C p->li nk=p->li nk;D p=p->li nk->li nk;21、设单循环链表中结点的结构为（data,link ）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。
若想删除链表第一个结点，则应执行下列哪一个操作（D ）A s=rear; rear=rear->li nk; delete s;B rear=rear->li nk; delete rear;C rear=rear->li nk->li nk; delete rear;D s=rear->link->link; rear->link->link=s->link; delete s; s 为第一个结点硫22、设单循环链表中结点的结构为（data,link ）,且first 为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（D ）。
A curre nt->li nk =nullB first->li nk=curre ntC first=curre ntD curre nt->li nk=first？23、一个栈的入栈序列为a，b，c，贝U出栈序列不可能的是（C ）。
A c,b,aB b,a,cC c,a,bD a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是（A ）。
A top=0B top=maxSizeC top=maxSizeD top=-125、栈和队列的共同特点是（C ）。
A 都是先进后出B 都是先进先出C 只允许在端点处插入和删除D没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为（D ）.A f+仁=rB 叶仁=fC f= =0D f= =r27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）A n-2B n-1C nD n+128、当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A top++;B top--;C top=0;D top;29、设链式栈中结点的结构为（data, link ）,且top是指向栈顶的指针。
若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（A ）操作。
A x=top->data; top=top->li nk;B top=top->li nk; x=top->data;C x=top; top=top->li nk;D x=top->data;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int fron t, rear;} Queue;若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句（D ）A Q.fro nt= = Q.rear;B Q.fro nt - Q.rear= = Maxsize;C Q.fro nt + Q.rear= = Maxsize;D Q.fro nt= = （Q.rea 叶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 (int n) {if (n<=3) retur n 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 ooB 3C 2D 534广义表A(a),则表尾为(C)、A a B(()) C空表D(a)35下列广义表是线性表的有(C)、A E(a,(b,c))B E(a,E)C E (a,b)D E(a ,L())36、递归表、再入表、纯表、线性表之间的关系为( C )A 再入表＞递归表〉纯表〉线性表B 递归表〉线性表＞再入表〉纯表C 递归表＞再入表〉纯表〉线性表D递归表〉再入表＞线性表〉纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B ）的二叉树。
A空或只有一个结点B高度等于其结点数C任一结点无左孩子 D 任一结点无右孩子38、对于任何一棵二叉树T,如果其终端结点数为n。
，度为2的结点为n2.，则（A ）A n o= n?+1B n 2= n o+1C n 0= 2n 2+1D n 2=2n o+139、由权值分别为11, 8, 6, 2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）A 24B 73C 48D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为dal,则第I个结点的地址为（ A ）。
A da1+（l-1）*mB da1+I*mC da1-I*mD da1+（l+1）*m41、34具有35个结点的完全二叉树的深度为（A ）A 5B 6C 7D 842、对线性表进行折半搜索时，要求线性表必须（ C ）A以链接方式存储且结点按关键码有序排列 B 以数组方式存储C以数组方式存储且结点按关键码有序排列D以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A散列存储 B 顺序存储或链接存储C压缩存储 D 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C ）A O （n2）B O （n log 2n）C O （log 2n）D O （n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为（A ）A nB n+1C n-1D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。