数据结构考试及答案()
数据结构考试及答案()
————————————————————————————————作者：————————————————————————————————日期：
2
数据结构试题
一、单选题
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; 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; 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 ） 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、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。 12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ） 13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。 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 ）个字符编码。 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））。 41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。 42、假定一个线性表为 （”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的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）之前插入一个新 元素时，需要向后移动多少个元素？ 答案：需要向后移动n- i + 1个元素 2、当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321 是否是合理的出栈序列？ 答案： 可能的出栈序列有 种，6457321不是合理的出栈序列。 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 的结点的父结点(若存在)的编号是多少? (3) 编号为i 的结点的第m 个孩子结点(若存在)的编号是多少? (4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h 是n 的什么函数关系? 答案： 4291 234567891011121314811717 14=*************=+C （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分）。 答案： A C D B F E K J G H I A C D B F E K J G H I 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试设计赫夫曼编码。 1 3 2 5 4 7 6 8 5 13 11 2 7 9 6 1 3 2 5 4 7 6 5 13 6 2 7 * + + + f + * + c b a h g d e 答案： 为方便起见，设各种字符的权值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, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图： 2 1 5 3 217 8 0 0 0 0 0 0 0 1 1 1 1 1 1 1 这棵二叉树的后序遍历序列为：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。 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。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 答案：折半搜索时的判定树为： A B F G E C D H J I 5 16 025 8 ASL =1/14（1+2*2+3*4+4*7）=45/14 SUCC =1/15（3*1+4*14）=59/15 ASL UNSUCC 五、算法分析题 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 ) 全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ 2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是 A．线性表 B．队列 C．树 D．图 2．计算n!(整数n≥0)的递归算法是：int Factorial(int n){if(n= =o)return l；else return n*Factorial(n--1)；}其时闯复杂度为 A．0(n) B．0(log2n) C．O(n0) D．O(n2) 3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A．p=q； B．p--：>next=q； C．q一>next=p--：>next；p-->next=q； D．p一>next—q；q-->next—p--：>next； 4. 设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是 A．sxxssxxs B．ssxsxxxs C．ssxxxssx D．sssxxxsx 5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是 A．顺序表 B．单链表C．栈 D．队列 6．设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为 A．O(n)、O(1) B．O(1)、O(1) C．O(1)、O(n) D．0(n)、0(n) 7．若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为 A．4 B．5 C．6 D．7 8．按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是 数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） 全国2005年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能 ．．．的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) 浙02142# 数据结构导论试题第 1 页（共 4 页） 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 数据结构》期末考试试题及答案 ( 2003-2004 学年第 2 学期 ) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 7．图的 Depth-First Search （DFS ） 遍历思想实际上是二叉树（ 法的推广。 （A ）、先序 （ B ）、中序 （C ）、后序 （D ）、层序 8．在下列链队列 Q 中，元素 a 出队的操作序列为（ p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9． Huffman 树的带权路径长度 WPL 等于（ c （ A ）、除根结点之外的所有结点权值之和1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 （ c ）。 （A ） 、正确性 （B ）. 可行性 （C ）. 健壮性 2．设 S 为 C 语言的语句 ,计算机执行下面算法时， for （i=n-1 ； i>=0 ； i--） for （j=0 ；j 全国2011年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（） A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是 （）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9.下列叙述中错误的是（） A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ “数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 全国2013年10月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．算法的时间复杂度表征的是 A．算法的可读性B．算法的难易程度 C．执行算法所耗费的时间D．执行算法所耗费的存储空间 2．对需要频繁插入和删除结点的线性表，适合的存储方式是 A．顺序储存B．链式存储 C．索引存储D．散列存储 3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．迪杰斯特拉(Dijkstra)算法的功能是 A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径 C．求图的最小生成树D．求图的拓扑排序序列 5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能 ．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2 C．1，2，3，4，5 D．5，4，3，2，1 6．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为 A．1015 B．1016 C．1028 D．1030 7．深度为4的完全二叉树的结点数至少为 A．4 B．8 C．13 D．15 8．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中 A．结点k对应行元素之和B．结点k对应列元素之和 C．结点k对应行和列元素之和D．非零元素之和 9．无向图G的邻接矩阵一定是 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 一、选择题（共15题，每题2分，共计30分） 1、单链表的一个存储结点包含（ C ） A.指针域和链域 B.指针域或链域 C.数据域或指针域 D.数据域和链域 2、采用线性链表表示一个向量时，要求占用的存储空间地址（ D ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、可连续可不连续 3、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。 A. n-2 B. n-1 C. n D. n+1 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A、s→next = p→next; p→next = s; B、p→next = s; s→next k = q; C、p→next = s→next; s→next = p; D、q→next = s; s→next = p; 5、在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。 A、 80 B、 100 C、 240 D、 270 6、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A、栈 B、队列 C、循环队列 D、优先队列 7、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 A、4, 3, 2, 1 B、2, 4, 3, 1 C、1, 2, 3, 4 D、3, 2, 1, 4 8.下述各类表中可以随机访问的是（D ）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 9.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（ B ）。 A. 21 B. 20 C. 19 D. 25 10.元素1，3，5按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。 A. 5 3 1 B. 5 1 3 C. 3 1 5 D. 1 5 3 11.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ A ）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 12．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。 A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL 13.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ B ）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 14.对如图1所示二叉树进行中序遍历，结果是（ A ）。 A. dfebagc B. defbagc C. defbacg D.dbaefcg 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A ) 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 自考数据结构重点(２０１4整理） 第一章概论 １、瑞士计算机科学家沃思提出：算法+数据结构=程序。算法就是对数据运算得描述，而数据结构包括逻辑结构与存储结构。由此可见，程序设计得实质就是针对实际问题选择一种好得数据结构与设计一个好得算法,而好得算法在很大程度上取决于描述实际问题得数据结构。 ２、数据就是信息得载体。数据元素就是数据得基本单位。一个数据元素可以由若干个数据项组成，数据项就是具有独立含义得最小标识单位.数据对象就是具有相同性质得数据元素得集合。 3、数据结构指得就是数据元素之间得相互关系，即数据得组织形式。 数据结构一般包括以下三方面内容：数据得逻辑结构、数据得存储结构、数据得运算 ①数据得逻辑结构就是从逻辑关系上描述数据,与数据元素得存储结构无关，就是独立于计算机得。 数据得逻辑结构分类:线性结构与非线性结构 ②数据元素及其关系在计算机内得存储方式，称为数据得存储结构(物理结构）。 数据得存储结构就是逻辑结构用计算机语言得实现，它依赖于计算机语言。 ③数据得运算。最常用得检索、插入、删除、更新、排序等。 4、数据得四种基本存储方法：顺序存储、链接存储、索引存储、散列存储 (１）顺序存储:通常借助程序设计语言得数组描述。 (2）链接存储：通常借助于程序语言得指针来描述。 （3）索引存储：索引表由若干索引项组成。关键字就是能唯一标识一个元素得一个或多个数据项得组合。 (4）散列存储：该方法得基本思想就是:根据元素得关键字直接计算出该元素得存储地址. 5、算法必须满足5个准则：输入,０个或多个数据作为输入;输出，产生一个或多个输出；有穷性，算法执行有限步后结束;确定性，每一条指令得含义都明确;可行性，算法就是可行得。 算法与程序得区别:程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定得符号语言来描述。目前常用得描述算法语言有两类:类Pascaｌ与类C. ６、评价算法得优劣:算法得"正确性＂就是首先要考虑得.此外,主要考虑如下三点：?①执行算法所耗费得时间，即时间复杂性； ②执行算法所耗费得存储空间，主要就是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性与可操作性。 以上几点最主要得就是时间复杂性,时间复杂度常用渐进时间复杂度表示。 7、算法求解问题得输入量称为问题得规模,用一个正整数n表示. 8、常见得时间复杂度按数量级递增排列依次为：常数阶０（1）、对数阶0(ｌog2n)、线性阶0（n）、线性对数阶0(nl ｏg2n）、平方阶0(n2）立方阶０（n3)、…、ｋ次方阶0（nｋ）、指数阶０(2ｎ)与阶乘阶0（ｎ！)。 ９、一个算法得空间复杂度Ｓ(ｎ）定义为该算法所耗费得存储空间，它就是问题规模ｎ得函数,它包括存储算法本身所占得存储空间、算法得输入输出数据所占得存储空间与算法在运行过程中临时占用得存储空间。 第二章线性表 1、数据得运算就是定义在逻辑结构上得，而运算得具体实现就是在存储结构上进行得. 2、只要确定了线性表存储得起始位置,线性表中任意一个元素都可随机存取,所以顺序表就是一种随机存取结构。 3、常见得线性表得基本运算： (1)置空表ＩnｉtLiｓt（L) 构造一个空得线性表L。 （2）求表长ＬistLｅngtｈ（L)求线性表L中得结点个数,即求表长。 （3)GetＮｏde(L,ｉ）取线性表L中得第i个元素.?（4)LoｃateNode(L，x）在L中查找第一个值为x 得元素，并返回该元素在L中得位置。若L中没有元素得值为x ,则返回0值。?(5）ＩnｓerｔList(L,ｉ，x)在线性表Ｌ得第i个元素之前插入一个值为x 得新元素,表Ｌ得长度加１. （6)DeletｅＬｉｓt(L，i)删除线性表L得第i个元素,删除后表L得长度减1. 4、顺序存储方法：把线性表得数据元素按逻辑次序依次存放在一组地址连续得存储单元里得方法。 顺序表(Sequeｎtial Lisｔ):用顺序存储方法存储得线性表称为顺序表.顺序表就是一种随机存取结构，顺序表得特点就是逻辑上相邻得结点其物理位置亦相邻。 5、顺序表上实现得基本运算: 全国20XX 年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)l A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为???? ??????010100110，则该图中顶点V 1的出度为（ C ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，A C.E ，A ，B ，C ，D D.E ，D ，C ，B ，A 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ A ） A.O （1） B.O （log 2n ） C.O （n ） D.O (n 2) 7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ B ） A.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ B ） A.O (1) B.O (n) C.O (n ) D.O (log 2n)全国自学考试数据结构导论试题及答案(4套)
02142数据结构导论201604
数据结构考试试题及答案
自考数据结构导论20051年10月试卷
2017年数据结构期末考试题及答案A
《数据结构》期末考试试题及答案
自考数据结构试题真题
数据结构C语言版期末考试试题(有答案)
自考数据结构导论复习资料
数据结构复习资料,java数据结构期末考试
数据结构期末考试试题及答案
全国2013年10月高等教育自学考试数据结构
《数据结构》期末考试题及答案
数据结构考试题
自考数据结构导论
《数据结构》期末考试试卷
自学考试数据结构重点总结
全国数据结构导论10月高等教育自学考试试题与答案