数据结构前四章选择题.doc

第一章

第01题:要表示高校的校，系，班级的有关数据及其关系，选择___比较合适。【 福建 2009 专升本】
A) 图结构 B) 集合结构 C) 线性结构 *D) 树结构
第02题:一个算法的定义是____。 【中山大学 1998 二、1】
A) 满足五个基本特性的东西 *B) 问题求解步骤的描述 C) 程序
第03题:算法的计算量的大小称为计算的_____【北京邮电大学2000 二、3 】
*A) 复杂性 B) 效率 C) 现实性 D) 难度
第04题:算法的时间复杂度取决于_____【中科院计算所 1998 二、1】
*A) 和问题的规模及待处理数据的初态有关 B) 仅和待处理数据的初态有关
C) 仅和问题的规模有关 D) 和问题的规模、待处理数据的初态、CPU的执行速度有关
第05题:算法的复杂性与算法描述语言无关，但与所用计算机有关。这句话____
*A) 错误 B) 正确
第06题:算法的可行性是指序列的每一项运算都有明确的定义，无歧义。这句话___
A) 正确 *B) 错误
第07题:算法对输入和输出的要求是____
A) 算法的输入输出都只能有1个
*B) 算法可以没有输入，但必须有至少一个输出
C) 算法可以没有输出，但必须有至少一个输入
D) 算法必须有1到多个输入，1到多个输出
第08题:以下数据结构中，____是非线性数据结构。 【中山大学 1999 一、4】
A) 栈 B) 队列 C) 字符串 *D) 树
第09题:以下与数据的存储结构无关的术语是__。【北方交通大学 2000 二、1】
A) 循环队列 *B) 栈 C) 双链表 D) 单链表
第10题:以下哪一个术语与数据的存储结构无关__ 【 福建 2007 专升本】
A) 双向链表 *B) 队列 C) 线索二叉树 D) 静态数组
第11题:请阅读下面的代码:
func(int n)
{
int i,j,x=0;
for(i=0;i<n;i++)
x++;
}
func函数在最坏情况下的时间复杂度为____
A) O(n*n) *B) O(n) C) O(1) D) O(n*n*n)
第12题:请阅读下面的代码:
func(int n)
{
int i,j,k,x=0;
for(i=0;i<n;i++) x++;
for(j=0;j<n;j++) x++;
for(k=0;k<n;k++) x++;
}
func函数在最坏情况下的时间复杂度为____
A) O(1) *B) O(n) C) O(n*n) D) O(n*n*n)
第13题:请阅读下面的代码:
func(int n)
{
int i,j,x=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x++;
}
func函数在最坏情况下的时间复杂度为____
*A) O(n*n) B) O(1) C) O(n*n*n) D) O(n)
第14题:请阅读下面的代码:
func(int n)
{
int i,j,k,x=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
x++;
}
func函数在最坏情况下的时间复杂度为____
A) O(n*n) B) O(1) *C) O(n*n*n) D) O(n)
第15题:ADT表中，ADT是下列四个选项中___的缩略语
*A) Abstract Data Type B) Atlantic Daylight Time
C) Adaptive Dynamic Threshold D) Automatic Data Transmission
第2章

第16题:线性表是一个__【 福建 2009 专升本】
A) 有限序列，不能为空 B) 无限序列，不能为空
C) 无限序列，可以为空 *D) 有限序列，可以为空
第17题:指针实现表的查询函数(查找第K个位置上元素ListRetrive)在平均情况下的时间复杂度为___
A) O(1) *B) O(n) C) O(log(n)) D) O(n*n)
第18题:线性表的特点是每个元素都有一个前驱和一个后继。这句话___【合肥工业大学2001 二、1】
A) 正确 *B) 错误
第19题:数组实现表的添加、删除元素的函数在最好情况下的时间复杂度为___
A) O(log(n)) B) O(n*n) C) O(n) *D) O(1)
第20题:数组实现表的添加、删除元素的函数在最坏情况下的时间复杂度为___
A) O(1) B) O(n*n) C) O(log(n)) *D) O(n)
第21题:数组实现表的添加、删除元素的函数在平均情况下的时间复杂度为___
A) O(log(n)) *B) O(n) C) O(n*n) D) O(1)
第22题:单链表在指针P所指结点之后增加结点的时间复杂度为____
A) 最坏O(n),最好O(1) B) O(n) C) 最坏O(n),平均O(1) *D) O(1)
第23题:数组实现表的查询函数(查找第K个位置上元素ListRetrive)在平均情况下的时间复杂度为___
A) O(n) *B) O(1) C) O(K) D) O(log(n))
第24题:在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的移动次数为__【 福建 2007 专升本】
*A) n-i+1 B) i C) i-1 D) n-i
第25题:数组实现表有24个元素，进行插入操作的过程中，平均移动元素的次数为____
*A) 12 B) 11.5 C) 24 D) 1
第26题:数组实现表36个元素,进行删除操作的过程中,平均移动元素的次数为____
A) 18 B) 1 *C) 17.5 D) 35
第27题:顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。这句话___【北京邮电大学 2002 一、2】
*A) 错误 B) 正确
第28题:下述哪一条是顺序存储方式的优点__【 福建 2007 专升本】
A) 可方便地用于各种逻辑结构的存储表示 B) 删除运算方便
*C) 存储密度大 D) 插入运算方便
第29题:若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用____存储方式最节省时间。【哈尔滨工业大学 2001 二、1】
*A) 顺序表 B) 双链表 C) 单循环链表 D) 带头结点的双循环链表
第30题:某链表中最常见的操作是在已知的一个结点之前插入一个新的结点和删除其之前一个结点，则采用 ___存储方式最节省运算时间【 福建 2009 专升本】
A) 带尾指针的单向链表 B) 单向循环链表 C) 带头指针的单向链表 *D) 双向链表
第31题:对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为__【 福建 2007 专升本】
A) 用头指针表示的单循环链表 B) 单链表
*C) 用尾指针表示的单循环链表 D) 顺序表
第32题:下列关于表ADT函数的说法，正确的是_______
A) ListEmpty函数的返回值不可能是0
B) ListLocate函数的返回值不可能是0
*C) ListDelete(int k,List L)函数的k参数不可以为0
D) ListInsert(int k,ListItem x,List L)函数的k参数不可以为0
第33题:如果表L中的元素为happy,执行ListInsert(3,ListDelete(2,L),L)后，表的元素是___
A) hppy B) happy C) happy *D) hppay
第34题:下列关于数组实现表判空函数的实现代码中，错误的是____
A) if(L->n)return 0;else return 1; B) return L->n==0;
*C) return L->n=0; D) if(L->n==0)return 1;else return 0;
第35题:单链表中有n个结点,在其中查找值为x的结点,查找成功时,需比较的
平均次数是___【 福建 2006 专升本】
A) n B) n/2 C) (n-1)/2 *D) (n+1)/2
第36题:线形表采用链式存储时,结点的存储地址____【 福建 2006 专升本】
A) 和头结点的存储地址相连续 B) 必须是不连续的
*C) 连续与否均可 D) 必须是连续的
第37题:线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。这句话___
A) 错误 *B) 正确
第38题:链表不具有的特点是____ 【福州大学 1998 一、8 】
*A) 可随机访问任一元素 B) 插入、删除不需要移动元素
C) 不必事先估计存储空间 D) 所需空间与线性长度成正比
第39题:用单链表表示的链式队列的队头在链表的_____位置。【清华大学 1998 一、1】
*A) 链头 B) 链中 C) 链尾
第40题:在循环链表中,从任意一个单元出发可以找到表中其它单元。这句话___
A) 错误 *B) 正确
第41题:在一个以head指向首元素的单循环链中(带头结点)，p指针指向链尾的条件是___【南京理工大学1998 一、15】
A) p->data=-1 *B) p->next->next=head C) p->next=head D) p->next=NULL
第42题:对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是____
A) head->next==head B) head!=NULL C) head==NULL *D) head->next==NULL
第43题:单链表(无头结点)中，结点p所指向的结点有前驱结点的条件是___
*A) p!=L->first B) p==L->first C) p!=NULL D) p->next!=NULL
第44题:在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：____【青岛大学 2001 五、3】
A) p->next=s;p->next=s->next; B) p->next=s;s->next=p->next;
C) p->next=s->next;p->next=s; *D) s->next=p->next;p->next=s;
第45题:已知单链表结点构造为
struct node
{
int data;struct node *next;
} *p,*q,*r;
删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是___
【 福建 2006 专升本】
*A) r=p->next;p->next=q->next; B) p->next=p->next->next;
C) q=p->next;r=q->next;p->next=r; D) q=p->next;p->next=q->next;
第46题:链表的结点类型定义如下:
typedef struct node *link;
struct node
{
ListItem element;
link left;
link right;
}*p,*q,*r;
删除双链表中结点p(由p指向的结点)的操作是___【 福建 2008 专升本】
A) q=p->left;r=p->right;q->right=r->left; *B) q=p->left;r=p->right;q->right=r;r->left=q;
C) q=p->left;r=p->right;q->left=r;r->right=q; D) q=p->right;r=p->left;q->right=r;r->left=q;
第3章

第47题:对于栈操作数据的原则是___。【青岛大学 2001 五、2】
A) 后进后出 B) 先进先出 C) 不分顺序 *D) 后进先出
第48题:栈实现过程中，通常采用的两种存储方式是____
A) 线性存储和非线性存储 *B) 顺序存储与链表存储 C) 索引存储与散列存储
第49题:栈和队都是_____【南京理工大学 1997 一、3】
*A) 限制存取点的线性结构 B) 限制存取点的非线性结构
C) 顺序存储的线性结构 D) 链式存储的非线性结构
第50题:设计一个判别表达式中左，右括号是否配对出现的算法，采用____数据结构最佳。【西安电子科技大学 1996 一、6】
A) 线性表的顺序存储结构 *B) 栈 C) 线性表的链式存储结构 D) 队列
第51题:递归方法实现递归算法时通常需要使用____【 福建 2008 专升本】
A) 循环队列 B) 双向队列 C) 二叉树 *D) 栈
第52题:递归过程或函数调用时，处理参数及返回地址，要用一种称为____的数据结构。【福州大学 1998 一、1】
*A) 栈 B) 队列 C) 多维数组 D) 线性表
第53题:栈在____中应用。【中山大学 1998 二、3】
*A) 其它三个选项都是正确的。 B) 表达式求值。 C) 递归调用。 D) 子程序调用。
第54题:一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是___。【中山大学 1999 一、9】
A) 不确定 B) n-i C) I *D) n-i+1
第55题:若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是___。【武汉大学 2000 二、3】
A) i-j-1 B) j-i+1 C) i-j *D) 不确定的
第56题:使用一个栈,每次限制进栈和出栈操作一个元素。
假设进栈的元素序列依次是a、b、c、d,指出不可能的出栈序列___【 福建2006专升本】
*A) adbc B) abcd C) dcba D) acbd
第57题:已知一个栈s以及一个输入序列（A，B，C，D，E），每个元素按照A，B，C，D，E顺序进栈一次，进栈后可立即出栈，也可在栈中停留一段时间后再
出栈，则不能得到 ___ 序列【 福建 2009 专升本】
*A) D，C，A，B，E B) C，B，A，D，E
C) B，A，E，D，C D) A，B，C，D，E
第58题:有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列____【 福建 2007 专升本】
A) 4,5,3,1,2,6 *B) 3,4,6,5,2,1 C) 2,3,4,1,5,6 D) 5,4,3,6,1,2
第59题:输入序列为ABC，可以变为CBA时，经过的栈操作为_____【中山大学 1999 一、8】
A) push,push,pop,pop,push,pop *B) push,push,push,pop,pop,pop
C) push,pop,push,pop,push,pop D) push,pop,push,push,pop,pop
第60题:123456789顺序入栈，如果已知出栈的第一个元素是6，那么出栈的第三个元素可能是:___
A) 1 B) 6 *C) 9 D) 3
第61题:设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是____【南京理工大学 2000 一、6】
*A) 3 B) 6 C) 4 D) 2
第62题:如果用数组data来实现栈,为降低复杂度,data[0]最好对应___
A) 栈顶 *B) 栈底
第63题:如果用单链表来实现栈,为降低复杂度,表首结点最好对应____
*A) 栈顶 B) 栈底
第64题:在用一个数组实现两个栈AB共存的过程中，应在数组的左右两端放置____
A) 左端(下标0端)放栈底,右端放栈顶 B) 栈顶
*C) 栈底 D) 左端(下标0端)放栈顶,右端放栈底
第65题:6个元素依次进栈,出栈的顺序共有____种
A) 120 B) 121 *C) 132 D) 36
第66题:存在一种栈的实现方法，能够使入栈、出栈、返回栈顶元素的操作都在O(1)的时间内完成。这句话____
*A) 正确 B) 错误
第67题:栈的Push函数的作用是____
*A) 放入元素到栈顶 B) 放入元素到栈底
C) 返回并删除栈顶元素 D) 清空栈
第68题:在用数组实现栈的过程中,入栈操作和出栈操作正确的是_____
A) S->data[++S->top]=x;x=S->data[--S->top]; B) S->data[S->top++]=x; x=S->data[S->top--];
*C)S->data[++S->top]=x;x=S->data[S->top--];D) S->data[S->top++]=x; x=S->data[--S->top];
第4章

第69题:队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。这句话____【上海海运学院 1998 一、3】
*A) 错误 B) 正确
第70题:栈和队列都是限制存取点的线性结构。这句话____【中科院软件所 1999 六、(5)】
A) 错误 *B) 正确
第71题:栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。这句话____【上海海运学院 1999 一、2】
*A) 正确 B) 错误
第72题:栈和队列的共同点是______【燕山大学 2001 一、1】
A) 都是先进后出 B) 没有共同点
*C) 只允许在端点处插入和删除元素 D) 都是先进先出
第73题:对于队列操作数据的原则是___。
*A) 先进先出 B) 后进先出
C) 任意顺序 D) 先进后出
第74题:循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是____。【南京理工大学 2001 一、5】
*A) (rear-front+m)%m B) rear-front
C) rear-front-1 D) rear-front+1
第75题:无论如何实现，也无法使队列的入队、出队两个操作的时间复杂度同时将为O(1)。这句话____
A) 正确 *B) 错误
第76题:通常使用队列来处理函数或过程的调用。这句话___【南京航空航天大学 1997 一、5】
*A) 错误 B) 正确
第77题:双端队列在逻辑上是队列。这句话____
A) 正确 *B) 错误
第78题:如果队列Q中的元素为ABCD,执行QueueLast(Q)后，队列的元素是___
*A) ABCD B) ABCDD C) ABC D) BCD
第79题:会引起循环队列队头位置发生变化的操作是___【 福建 2008 专升本】
A) 取队首元素 B) 入队列 C) 取队尾元素 *D) 出队列
第80题:若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，
rear和front的值分别为______【浙江大学1999 四、1】
A) 4和2 B) 1和 5 C) 5和1 *D) 2和4
第81题:设数组queue[m]作为循环队列Q的存储空间,front为队头指针,rear为队尾指针,
则执行出队操作后其头指针front的值为___【 福建 2006 专升本】
A) front=(front-1)%m B)front=(front+1)%(m-1) C) front=front+1 *D) front=(front+1)%m
第82题:用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时____【北京理工大学 2001 六、3】
A) 仅修改队尾指针 B) 仅修改队头指针
*C) 队头,队尾指针都可能要修改 D) 队头、队尾指针都要修改
第99题:Jose排列问题定义如下：n个人排成环形，给定整数m,从第1个人开始数，沿环计数，每遇到m个人就让其出列，计数继续进行下去，直至剩下最后一个人为止，最后一个人为优胜者。这个排列称为一个(n,m)的Josephus排列。(约瑟夫环)
请问：(8,5)的优胜者是___
A) 6 *B) 3 C) 5 D) 8