数据结构基础题
- 格式：doc
- 大小：691.00 KB
- 文档页数：17
第一章 数据结构概述
一、选择题
1、数据结构被形式地定义为（D，R），其中D是_①_的有限集，R是D上的_② 有限集。
① A、算法 B、 数据元素 C、数据操作 D、逻辑结构
② A、操作 B、 映像 C、存储 D、关系
2、线性结构的顺序存储结构是一种_______的存储结构，线性表的链式存储结构是一种___的存储结构
A、随机存取 B、 顺序存取 C、索引存取 D、散列存取
3、计算机算法指的是___①____，它必须具备输入、输出和__②__等5个特征。
① A、计算方法 B、排序方法C、解决问题的有限运算序列 D、调度方法
② A、可执行性、可移植性和可扩充性 B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性
4、线性表的逻辑顺序与存储顺序总是一致的，这种说法是_______
A、正确 B、 错误
5、每种数据结构都具有三个基本运算：插入、删除和查找，这种说法_______
A、正确 B、 错误
6、下列算法是时间复杂度是（ ）
for(i=0;i
for(j=0;j
c[i][j]=i+j;
A、 O（1）B、O（n）C、O（log2n）D、O（n2）
7、算法指的是（ ）
A、 计算机程序B、解决问题的答案C、排序算法D、解决问题的有限运算序列
8、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B、在第i个结点后插入一个新结点（1≤i≤n）
C、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
9、1. 算法分析的两个主要方面是（ ）
A、数据复杂性和程序复杂性 B、可读性和文档性
C、时间复杂度和空间复杂度 D、正确性和简单性
10、下列算法的时间复杂度是（ ）
i=1；j=0；
while (i+j<=n)
{ if(i>j) j++；
else i++； }
A、O（1）B、 O（n）C、O（log2n） D、O（n2）
11、
二、填空题
1、 数据的逻辑结构包括____①___、___②___和___③____三种结构，树形结构和图形结构合称为_____④_____。
2、 在线性结构中，第一个结点__①___前驱结点，其余每个结点有且只有__②__个前驱结点，最后一个结点__③__后续结点，其余每个结点有且只有_④__个后续结点。 3、 在树形结构中，树根结点没有___①___结点，其余每个结点有且仅有_②__个前驱结点；叶子结点没有__③___结点，其余每个结点的后续结点可以___④____。
4、 在图形结构中，每个结点的前驱结点数和后续结点数可以___①____。
5、 线性结构中元素之间存在____①___关系，树形结构中元素之间存在____②__关系，兔形结构中元素之间存在___③___关系。
6、 下面程序段的时间复杂度是________
for ( i =0; i
for (j=0; j
A[i][j]=0;
7、数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。
8、在计算机中存储数据结构时不仅要存储数据元素的值，还要存储数据元素之间的 。
9
参考答案
一、选择题
1、①B ②D 2、 ①A ②B 3、 ①C ②B 4、 B 5、B
二、填空题
1、线性结构、树形结构 、图形结构 、非线性结构 2、没有、1、没有、1
3、前驱、1、后续、任意多个 4、任意多个 5、一对一、一对多、多对多 6、O(m*n)
第二章 线性表
一、单项选择题
1、 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是______
A、110 B、108 C、100 D、120
2、 一个栈的入栈序列是a、b、c、d、e，则栈不可能的输出顺序是______
A、edcba B、decba C、dceab D、abcde
3、 若已知一个栈的入栈序列是1，2，3，……，n，其输出序列为p1，p2，p3，……pn，若p1=n,则pi=________
A、i B、n=i C、n-i+1 D、不确定
4、 判定一个顺序栈ST(当前分配的存储单元个数为M0)为空的条件是：_______
A、ST.TOP！=0 B、ST.TOP==0 C、ST.TOP！=M0 D、ST.TOP= =ST.BASE
5、 判定一个顺序栈ST(当前分配的存储单元个数为M0)为满的条件是：_______
A、ST.TOP！=M0 B、ST.TOP==0 C、ST.BASE！=M0 D、ST.TOP-ST.BASE=M0
6、 一个队列的入列序列是1，2，3，4，则队列的输出序列是_______
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1
7、 判断一个顺序队列QU（最多的元素个数为m0）为空的条件是______
A、QU.rear-QU.front==m0 B、QU.rear-QU.front-1==m0
C、QU.front= =QU.rear D、QU.rear+1=QU.front
8、 判断一个顺序队列QU（最多的元素个数为m0）为满的条件是______
A、QU.rear-QU.front==m0 B、(QU.rear+1)%m0= =QU.front C、QU.front= =QU.rear D、QU.rear+1=QU.front
9、 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数为_______
A、(rear-front+m)%m B、rear-front+1 C、rear-front-1 D、rear-front
10、栈和队列的共同点是_____
A、都是先进后出 B、都是先进先出
C、只允许在端点处插入和删除元素 D、没有共同点
11、表达式a*(b+c)-d的中缀表达式是______
A、abcd*+- B、abc+*d- C、abc*+d- D、-+*abcd
12不带头结点的单链表head为空的判定条件是：__________
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
13带头结点的单链表head为空的判定条件是-__________
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
14非空的循环单链表head的尾结点（由P所指向）满足_______
A、p.next= = NULL B、p= = NULL
C、p.next= = head D、p= =head
15、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较______个结点。
A、n B、n/2 C、(n-1)/2 D、(n+1)/2
16、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_____
A、O(1) B、O(n) C、O(n2) D、O(nlog2n)
17、线性结构中，只有一个直接前驱和一个直接后继的结点是（ ）
A、 第一个结点 B、最后一个结点
C、中央的结点 D、除第一个和最后一个之外的所有结点
18、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果这六个元素的出栈顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是（ ）
A、3 B、4 C、5 D、6
19、非空的循环单链表head的尾结点（由p指向）满足（ ）
A、p->next= =null B、p= =null
C、p->next= =head D、p= =head
20、可以借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系的存储表示方法是（ ）
A、 顺序存储结构B、 链式存储结构C、 索引存储结构D、散列存储结构
21、与线性表的链式存储结构相符的特性是（ ）
A、可以随机访问 B、不需要另外开辟空间来保存元素间的关系
C、存储空间静态分配 D、插入和删除操作灵活
22、 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A、 8 B、63.5 C、63 D、7
23、设一个栈的入栈序列是a，b，c，d，e，f，则不可能的出栈序列是（ ）。
A、c，b，e，f，d，a B、a，e，d，f，b，c C、b，d，c，e，a，f D、d，e，c，f，b，a
24、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）
A、必须是连续的 B、部分地址必须是连续的
C、一定是不连续的 D、连续或不连续都可以
25、
二、填空题
1、 在一个长度为n的向量中的第 i个元素(1<= i <=n)之前插入一个元素时，需向后移动______个元素。
2、 在一个长度为n的向量中删除第i个元素时，需要向前移动______个元素。
3、 在具有n个单元的循环队列中，队满是共有______个元素。
4、 栈的特点是______，队列的特点是________
5、 在顺序表中插入或删除一个元素，需要平均移动（ ）个元素，具体移动的元素个数与（ ）有关。
6、 顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。
7、 一个队列的入队序列是1,3,5,7,9，则出队的输出序列只能是
8、 线性表、栈和队列都是 性数据结构；可以在线性表的 位置插入和删除元素；对于栈应在 位置插入和删除元素；对于队列应在 位置插入元素，在 位置删除元素。
9、
参考答案
一、选择题
1、B 2、C 3、C 4、D 5、D 6、B 7、C 8、A 9、A 10、C 11、B
12、A 13、B 14、C 15、D 16、B
二、填空题
1、n-i+1 2、 n-i 3、 n-1 4 、 后进先出、先进先出
第三章 链表
一、选择题
1、 向一个栈顶指针为HS的链栈中插入一个s所指结点时，应执行________
A、HS.next= s B、s.next = HS.next ;HS.next= s
