数据结构试题
一、单选题
1、在数据结构的讨论中把数据结构从逻辑上分为（C ）
A 内部结构与外部结构
B 静态结构与动态结构
C 线性结构与非线性结构
D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）
A 必须是连续的
B 部分地址必须是连续的
C 一定是不连续的
D 可连续可不连续
3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A n
B n/2
C (n-1)/2
D (n+1)/2
4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A 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 ）。
A 求子串
B 模式匹配
C 串替换
D 串连接
7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。
A 80
B 100
C 240
D 270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈
B 队列
C 循环队列
D 优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % m
B ( rear - front + 1) % m
C ( front - rear + m) % m
D ( rear - front + m) % m
11、一个数组元素a[i]与（ A ）的表示等价。
A *（a+i）
B a+i
C *a+i
D &a+i
12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。
A 指针
B 引用
C 值
D 变量
13、下面程序段的时间复杂度为（ C ）
for (int i=0;i for (int j=0;j a[i][j]=i*j; A O(m2) B O(n2) C O(m*n) D O(m+n) 14、下面程序段的时间复杂度为（ B ） int f(unsigned int n) { if(n= =0 || n= =1) return 1; else return n*f(n-1); } A O(1) B O(n) C O(n2) 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->link=p;p->link=s; B s->link=p->link;p->link=s; C s->link=p->link;p=s; D p->link=s;s->link=p; 19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ B ）A s->link=p->link; p->link=s; B q->link=s; s->link=p C 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; 3 B p=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为第一个结点硫 22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。 A current->link =null B first->link=current C first=current D current->link=first ？23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。 A c,b,a B b,a,c C c,a,b D a,c,b 24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。 A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是( C )。 A 都是先进后出 B 都是先进先出 C 只允许在端点处插入和删除 D 没有共同点 26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ). A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ） A n-2 B n-1 C n D n+1 28、当利用大小为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->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 data[Maxsize]; Int front, rear; } Queue; 若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句 （ D ） A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; 5 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)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对 32、设有一个递归算法如下 int x (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 ∞ B 3 C 2 D 5 34、广义表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 0，度为2的结点为n 2 .,则 ( A ) A n 0= n 2 +1 B n 2 = n +1 C n 0= 2n 2 +1 D n 2 =2n +1 39、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ） A 24 B 73 C 48 D 53 40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。 A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 41、34 具有35个结点的完全二叉树的深度为( A ) A 5 B 6 C 7 D 8 42、对线性表进行折半搜索时，要求线性表必须（ C ） 7 A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储 43、顺序搜索算法适合于存储结构为（ B ）的线性表。 A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储 44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ） A O（n2） B O（n log 2n） C O（log 2 n） D O（n） 45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A ) A n B n+1 C n-1 D n+e 46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。 A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法 47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A ) A 1 B 2 C 9 D 10 48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ） A O（log 2 n） B O（n） C 不直接依赖于n D 上述都不对 二、填空题（） 1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种 2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种 3、一种抽象数据类型包括（数据）和（操作）两个部分。 4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、栈、队列逻辑上都是（线性存储）结构。 6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关 系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。 7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出） 8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。 9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。 10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。 11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这个位置上。从一个顺序栈删除元素时，需要前移一位 14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。 15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（2*i+2 ），双亲结点（i>=1）为（「(i-1)/2 ┐）. 16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。 17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元， 第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。 18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码 为0和10外，还可以最多对（ 4 ）个字符编码。 9 19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。 20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。 22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235） 23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。 24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（５），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。 25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。 26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。 27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是(1044)。 28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。 29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。 30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为 （n） 31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。 32、处理冲突的三种方法，分别为(线性探测)、（随机探测）、（链地址法）。 33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（Ｏ（n2））、利用克鲁斯卡尔算法产生的最小生成树， 其时间复杂度为（Ｏ（elog 2 e）） 34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog 2 n）），在最坏情况下的 时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log 2 n）），在最坏情况下的空间复杂度为（Ｏ（n））。 35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８４６５６７９］［４０８０］） 36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８４０］４６［５６７９８０］）。 37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最大值）称为树的度。 38、设K i =K j (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中R i 领先于R j (i 若排序后的序列中R i 仍领先于R j ，则这种排序方法是（稳定的），反之是（不稳 定的）。 40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ （log 2n）），整个排序过程的时间复杂度为（Ｏ（nlog 2 n））。 11 41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。 42、假定一个线性表为 （”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”a ayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为（３），（３），（２）。 43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１） 45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。46、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n 表示待散列存储的元素的个数，则α等于（n/m）。 47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。 48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。 三、判断题 四、运算应用题 1、在一个有n个元素的顺序表的第i个元素（1 ≤i≤n）之前插入一个新 元素时，需要向后移动多少个元素？ 13 答案：需要向后移动 n- i + 1个元素 2、 当一个栈的进栈序列为时，可能的出栈序列有多少种？是否是合理的出栈序列？ 答案： 可能的出栈序列有 种，不是合理的出栈序列。 4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案： ASL succ = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7 5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n 层；它有1个叶结点，n-1个分支结点。 6、 一棵高度为h 的满k 叉树有如下性质: 第h 层上的结点都是叶结点, 其余各层上每个结点都有k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i 的结点的父结点(若存在)的编号是多少? 4291 234567891011121314811717 14=*************=+C (3) 编号为i 的结点的第m 个孩子结点(若存在)的编号是多少? (4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h 是n 的什么函数关系? 答案： （1）各层的结点个数是k i (i=0,1,2,....,h) （2）编号为i 的结点的父结点(若存在)的编号是└ (i+k-2)/k 」 （3）编号为i 的结点的第m 个孩子结点(若存在)的编号是(i-1)*k+m+1 （4）当(i-1)%k<>0时有右兄弟， 右兄弟的编号为 i+1 （5）若结点个数为 n ，则高度h 和n 的关系为：h=log k (n*(k-1)+1)-1 (n=0时h=-1) 9、题目：11、将下面的森林变换成二叉树（7分）。 答案： 10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分） 答案： 12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分） 答案: 13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案： 为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示： 赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010 概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10 概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111 14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图： 这棵二叉树的后序遍历序列为：EDCBIHJGFA 15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。 16、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n 个结点的AVL树, 其最大高度是多少? 最小高度是多少? 答案：设高度为h(空树的高度为-1)的AVL树的最少结点为N h ，则N h = F h+3 -1。 17 F h 是斐波那契数。又设AVL 树有n 个结点，则其最大高度不超过3/2*log 2(n+1), 最小高度为「log 2(n+1) ┐-1。 17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 ASL SUCC =1/14（1+2*2+3*4+4*7）=45/14 ASL UNSUCC =1/15（3*1+4*14）=59/15 五、算法分析题 6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（7分） void demo2(LinkList head,ListNode *p) {//head 是带头结点的单链表，删除P 指向的结点 ListNode *q=head; while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head ”); q->next=p->next; free(p); } 10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法的处填入正确的语句。 int symmetry(DblList DL) { int sym=1; DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; } else sym=0; return sym;} 19 试卷 A 1、顺序表中所有结点的类型必须相同。（） 2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ） 3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2 4、Shell排序方法是不稳定的。（） 5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树( ) 6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效 率高。（） 7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。 8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构） 9、多维数组元素之间的关系是线性的。（） 10、任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( ) 11、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K 是__________，R是_____________。 12、广义表(a,(a,b),d,e,((i,j),k))的长度是。 13、一个串，除自身之外的所有子串都是该串的。 14、树形选择排序总的时间开销为。 15、按先根次序法周游树林正好等同于按周游对应的二叉 树。 16、外部路径长度E定义为从扩充二叉树的到每个 的路径长度之和。 17、在图结构中，如果一个从V p到V q的路径上除V p和V q可以相同外， 其它结点都不相同，则称此路径为一称为回路。 18、栈是一种表。 19．带权的又称为网络。 20、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11 的存储地址为LOC(a11)，矩阵的每个元素占一个存储单元，则a ij(i＝1， j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存储地 址为LOC(a ij)＝。 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A 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 ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 数据结构自测题1 一、单项选择题 1.线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以2.在单链表中，增加头结点的目的是为了（ C ） A．使单链表至少有一个结点B．表示表结点中首结点的位置 C．方便运算的实现D．说明单链表是线性表的链式存储实现 3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应是（ B ）A．2 B．3 C．4 D．5 4.树结构中，前驱结点与后继结点之间存在（ B ）关系。 A．一对一B．一对多C．多对一D．多对多 5.堆栈的特性描述是（ B ）。A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO 6.队列的特性描述是（ A ）。A．FIFO B．FILO C．FIFO和FILO D．FIFO或FILO 7.下列数据结构中，是非线性结构的是（ A ）A．树B．堆栈C．队列D．循环队列 8.设某个初始为空的容纳int型数据的堆栈进行了如下操作（每一步均未发生溢出）： push(1)、push(3)、pop()、push(6)、push(1)、pop()、push(3)、push(8) 后，该堆栈中从栈顶到栈底的元素依次为（ D ）A．8 1 8 3 B．1 3 1 8 C．1 6 3 8 D．8 3 6 1 二、判断题 1.二叉树可以为空树。（√） 2.顺序表和链表都是线性表。（√） 3.线性表的长度是线性表占用的存储空间的大小。（√） 4.队列只能采用链式存储方式。（×） 5.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。（√） 6.存在有偶数个结点的满二叉树。（×） 三、填空题 1.数据结构是数据在计算机内的组成形式和相互关系。 2.二叉树的三种遍历方式分别为中序遍历、先序遍历和后序遍历。 3.深度为K的满二叉树共有2k－1 个结点。 4.N个顶点的无向图是完全图的条件是其边数为n ( n－1 ) / 2 。 四、名词解释 1.ADT ADT是抽象数据类型的简称，指一个数学模型以及定义在该模型上的一组操作。 2.栈栈是限定仅在表尾进行插入或删除操作的线性表，具有先进后出（FILO）的特性。 3.队列队列是只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表，具有先进先出（FIFO）的特性。 五.简答题 1.分别写出下图所示二叉树的先序遍历、中序遍历和后序遍历序列 数据结构试卷 一、填空殖（每空1分共20分) 1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情 况。 2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作 为该完全二叉树的存储结构，则共有______501_____个空指针域. 3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。 4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和 等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。 5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。 6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为 ____e=d_____。 7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中 序或后序）. 8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较 _____7___次就可以断定数据元素X是否在查找表中。 9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为 ______1______。 10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第 i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。 11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一 趟快速排序结果为_____5 16 71 23 72 94 73______。 12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的 一种拓扑序列为___1 4 2 3___。 13.下列算法实现在顺序散列表中查找值为x的关键字,请在下划线处填上正确的语句。 struct record{int key；int others;｝; int hashsqsearch（struct record hashtable[ ],int k) { int i，j; j=i=k ％p； while （hashtable[j］。key!=k＆＆hashtable［j].flag！=0){j=（____）％m；if （i==j）return（-1)；} if （_______________________ ）return(j); else return(-1); 二、选择题（每题1分，共20分) 1．设某数据结构的二元组形式表示为A=(D，R)，D=｛01,02，03，04，05，06，07，08，09}，R={r}，r={〈01，02>，<01，03>,<01，04〉,<02，05〉，<02，06〉，〈03，07>，<03，08〉，〈03，09>｝，则数据结构A是（ B ）。 （A) 线性结构(B）树型结构(C) 物理结构(D）图型结构 2．下面程序的时间复杂为（B） for（i=1，s=0；i〈=n；i++）｛t=1；for(j=1；j〈=i;j++）t=t＊j；s=s+t；｝ (A） O(n) (B) O（n2) （C) O(n3）（D） O（n4） 3．设指针变量p指向单链表中结点A，若删除单链表中结点A,则需要修改指针的操作序列为（A ）。 (A） q=p—〉next；p-〉data=q->data;p—〉next=q—〉next；free(q); (B) q=p—〉next；q—>data=p-〉data；p-〉next=q->next;free（q）; 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog 2n+n 2+8）,其时间复杂度表示（ C ）。 A. O(n) B. O(nlog 2n) C. O(n 2) D. O(log 2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log 3n) D. O(n 3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 数据结构试卷（一) 一、单选题（每题2 分,共20分) 1.栈和队列的共同特点是( ）。 A.只允许在端点处插入和删除元素 B。都是先进后出 C。都是先进先出 D。没有共同点 2.用链接方式存储的队列，在进行插入运算时( ）。 A. 仅修改头指针 B。头、尾指针都要修改 C. 仅修改尾指针 D。头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？（） A. 队列B。栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A［0］[0]存放位置在644（10)，A[2]［2]存放位置在676（10），每个元素占一个 空间，问A［3]［3］（10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( ). A.有序数据元素 B.无序数据元素 C。元素之间具有分支层次关系的数据D。元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k—1 B.2K+1 C.2K—1 D。 2k—1 7.若有18个元素的有序表存放在一维数组A［19］中，第一个元素放A［1]中，现进行二分查找,则查找A［3］ 的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2,3 8.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A。 O（1）B。 O（n） C. O(1og2n） D。 O（n2） 9.对于线性表（7，34，55，25，64,46,20，10）进行散列存储时，若选用H(K）=K ％9作为散列函数，则散列 地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有（)条边才能确保是一个连通图. A。5 B.6 C.7 D。8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n）/n2,其数量级表示为________. 3.假定一棵树的广义表表示为A(C，D(E，F，G），H（I，J)），则树中所含的结点数为__________个,树的深度为 ___________，树的度为_________。 4.后缀算式9 2 3 +—10 2 / -的值为__________.中缀算式（3+4X）—2Y/3对应的后缀算式为 _______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址,有________________个指针是空指针. 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中,所含边结点分别有_______个和________ 个。 7.AOV网是一种___________________的图. 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________ 条边。 9.假定一个线性表为（12，23,74,55，63，40)，若按Key ％4条件进行划分，使得同一余数的元素成为一个子表， 则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为 ________. 12.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题（每题6 分，共24分) 1.在如下数组A中链接存储了一个线性表，表头指针为A [0］.next,试写出该线性表。 数据结构 1.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动个元素。 答：n-i+1 2.在一个长度为n的顺序表中删除第i个元素时，需要向前移动元素。 答： n-i 3.在单链表中设置头结点的作用是。 答：简单插入、删除算法 4.在单链中要删除某一指定结点，必须找到该结点的结点。 答：直接前驱 5.访问单链表中的结点，必须沿着依次进行。 答：指针域 6.在双链表中每个结点有两个指针域，一个指向，一个指向。 答：直接前驱结点，直接后继结点 7.在链表中，删除最后一个结点的算法时间复杂度为O(1)。 答：双向循环 8.访问一个线性表中具有给定值的时间复杂度的数量级是。 答：O(n) 9.由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为。答：O(n) ，O(n2) 10.在链表中，可以用表尾指针代替表头指针。 答：双向 11.在链表中，可以用表尾指针代替表头指针。 答：双向 12.根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是，最坏的情况是。 答：O(n) ，O(n2) 13.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是和。 答： O(1) , O(n) 14.在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 。 答：相同 15.在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 。 答：不相同 16.阐述顺序表和链表存储方式的特点。 答： 数据结构试题及答案 第一章 一、选择题 1、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 二叉树 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 试题1 一、单选题(每题 2 分,共20分） 1.1。对一个算法的评价,不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行（）。 A. p-〉next=HL—〉next；HL->next=p；B。p->next=HL； HL=p； C。p—〉next=HL；p=HL； D. HL=p；p->next=HL； 3. 3.对线性表，在下列哪种情况下应当采用链表表示?（） A。经常需要随机地存取元素B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A。2 3 1 B. 3 2 1 C。3 1 2 D。1 2 3 5.5。AOV网是一种（）. A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度( ）。 A．低于链接法处理冲突B。高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为( ）参数。 A．值B．函数C．指针D．引用 8.8。在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都 具有相同的( ）. A．行号B．列号C．元素值D．非零元素个数 9.9。快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O（nlog2n) C．0（n) D．0(n2） 10.10。从二叉搜索树中查找一个元素时，其时间复杂度大致为（)。 A. O(n）B。O（1） C. O(log2n) D。O(n2） 二、二、运算题（每题 6 分,共24分） 1. 1.数据结构是指数据及其相互之间的______________.当结点之间存在M 对N（M：N）的联系时,称这种结构为_____________________。 2.2。队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 数据结构试题(含答案) 数据结构试题(含答案) 一、选择题 1. 数据结构是计算机科学中的一个重要概念。下列选项中，不属于数据结构的是： A. 数组 B. 栈 C. 数据库 D. 链表 答案：C 2. 在数据结构中，栈(Stack)是一种后进先出(LIFO)的数据结构。下列操作中，不属于栈的是： A. 入栈 B. 出栈 C. 遍历 D. 清空栈 答案：C 3. 链表(Linked List)是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。下列选项中，不属于链表的是： A. 单链表 B. 双链表 C. 循环链表 D. 二叉树 答案：D 4. 哈希表(Hash Table)是一种根据关键码直接访问存储位置的数据结构。下列选项中，不属于哈希表的优点是： A. 快速查找 B. 插入和删除操作效率高 C. 数据无序 D. 冲突较少 答案：C 二、填空题 1. 树(Tree)是一种非线性数据结构，它由一组以边连接的节点组成。树中每个节点最多可以有________个子节点。 答案：无限制/任意个 2. 图(Graph)是由节点和连接节点的边组成的数据结构。图中节点的 度是指与该节点相连接的边的________。 答案：数量 3. 广度优先搜索(BFS)和深度优先搜索(DFS)是常用的图遍历算法。 在BFS中，使用________结构来保存待访问的节点。 答案：队列 4. 在二叉搜索树(Binary Search Tree)中，左子树中的每个节点的值 都小于根节点的值，右子树中的每个节点的值都大于根节点的值。这 种特性称为_______________。 答案：二叉搜索树性质 三、简答题 1. 请简要说明线性数据结构和非线性数据结构的区别。 答案：线性数据结构是指数据元素之间存在一对一的线性关系，例 如数组、栈、队列等；而非线性数据结构是指数据元素之间存在一对 多或多对多的关系，例如树、图等。线性数据结构的存储方式是连续的，非线性数据结构的存储方式是离散的。 2. 请解释栈和队列的基本原理，并说明它们的应用场景。 答案：栈(Stack)是一种后进先出(LIFO)的数据结构，只允许在栈的 一端进行插入和删除操作。栈的应用场景包括函数调用、表达式求值、 数据结构试题一及答案 一、单选题（每题2分，共40分） 1.数据结构中，与所使用的计算机无关的是数据的（）结构； A. 存储 B. 物理 C. 逻辑 D. 物理和存储 2.算法分析的目的是（） A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 3.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 4.链表是一种采用（）存储结构存储的线性表 A. 顺序 B. 链式 C. 星式 D. 网状 5.栈中元素的进出原则是（） A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出 6.串是一种特殊的线性表，其特殊性体现在（） A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符 7.设有两个串p和q，求q在p中首次出现的位置的运算称作（） A. 连接 B. 模式匹配 C. 求子串 D. 求串长 8.在循环队列中用数组A[m] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。 A. (front - rear + 1)% m B. (rear - front +1)% m C. (front - rear + m)% m D. (rear - front + m)% m 为第9.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A. 13 B. 33 C. 18 D. 40 10.将一棵树T转换为孩子—兄弟链表表示的二叉树H，则T的后序遍历是H的 数据结构考试题库含答案 数据结构考试题库含答 案 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存 储比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 数据结构试卷（一） 一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？(D) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素 占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。(C ) A．688 B．678 C．692 D．696 5.树最适合用来表示( C)。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( D ). k-1 A．2k-1 B.2K+1 C.2K-1 D. 2 7.设有6个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 一、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：正确性易读性强壮性高效率 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___O(n)__。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_9____个，树的深度为__3____，树的度为_3___。 4.后缀算式9 2 3 +- 10 2 / -的值为___-1___。中缀算式（3+4X）-2Y/3对应的后缀算式为3 4 X * + 2 Y * 3 / -_____________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有____2n ____个指针域，其中有__n-1 ______个指针域是存放了地址，有__________n+1______个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___e ___个和___2e____个。 7.AOV网是一种_____有向无回路______的图。 8.在一个具有n个顶点的无向完全图中，包含有__n(n-1)/2 ______条边，在一个具有n个顶点的有向完全图中，包含有___ n(n-1)_____条边。 1.9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为 一个子表，则得到的四个子表分别为__（12，40）__ （）____（74）____和__（23,55，63） 2.10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_增加1___。 二、运算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 数据结构习题答案一 评论:0 条查看:40 次zjw313014322发表于2009-04-21 16:25 一、选择题 1. 下面说法错误的是 C 。 （1）算法原地工作的含义是指不需要任何额外的辅助空间。 （2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2n)的算法。（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。 （4）同一个算法，实现语言的级别越高，执行效率越低。 A、（1） B、（1）（2） C、（1）（4） D、（3） 2. 一个递归算法必须包括 B 。 A、递归部分 B、终止条件和递归部分 C、迭代部分 D、终止条件和迭代部分 3. 数据的 C 包括查找、插入、删除、更新、排序等操作类型。 A、存储结构 B、逻辑结构 C、基本运算 D、算法描述 4. 在数据结构中，从逻辑上可以把数据结构分成 C 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 C 。 A、存储结构 B、存储实现 C、逻辑结构 D、运算实现 6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。 A、数据具有同一特点 B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C、每个数据元素都一样 D、数据元素所包含的数据项的个数要相等 7. 以下说法正确的是 D 。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同的逻辑结构 8. 以下说法错误的是 A 。 A、程序设计的实质是数据处理 B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式 C、运算实现是完成运算功能的算法或这些算法的设计 D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然 9. 下列程序段的时间复杂度为 B 。 x=n; y=0; while (x>=(y+1)*(y+1)) y=y+1; A、O(n) B、O(n1/2) C、O(1) D、O(n2) 10. 下列叙述中有关好的编程风格的正确描述是 C 。 A、程序中的注释是可有可无的 数据构造?自考复习考虑题○1 第一部分选择题(30分) 一、单项选择题〔本大题共15小题，每题2分，共30分〕在每题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．算法指的是〔D〕 A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址〔 B 〕 A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为〔 C 〕 A．O〔1〕 B．O〔n〕C．O〔m〕 D．O〔m+n〕4．由两个栈共享一个向量空间的好处是：〔 B 〕 A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，那么执行出队操作后其头指针front值为〔D〕 A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陈述中正确的选项是〔A〕 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 7．假设目的串的长度为n，形式串的长度为[n/3]，那么执行形式匹配算法时，在最坏情况下的时间复杂度是〔 C 〕10 A．O〔〕 B．O〔n〕C．O〔n2〕 D．O〔n3〕 8．一个非空广义表的表头〔D〕 A．不可能是子表B．只能是子表 C．只能是原子D．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，那么和以下行表( A ) 10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,那么度为0的结点个数为( C) A．4 B．5 C．6 D．7 11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D) A．e B．2e C．n2－e D．n2－2e 12．假设一个有n个顶点和e条弧的有向图用邻接表表示,那么删除与某个顶点vi相关的所有弧的时间复杂度是( C ) A．O(n) B．O(e) C．O(n+e) D．O(n*e) 13．用某种排序方法对关键字序列〔25，84，21，47，15，27，68，35，20〕进展排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84数据结构期末试题1及答案
数据结构试题及答案(1)
数据结构自测试题及答案
数据结构试题及答案(1)A
数据结构试题集[包含答案_完整版]
数据结构练习题(含答案)
十套数据结构试题及答案(1)
数据结构试题1
数据结构练习题及答案
数据结构试题1(有答案)
(完整word版)数据结构试题(含答案)
数据结构试题(含答案)
数据结构试题一及答案
数据结构考试题库含答案
数据结构试题及答案修改一
数据结构习题答案一
数据结构试题及答案1
相关主题
文本预览