数据结构导论选择
选择题
1. 在二维数组中，每个数组元素同时处于（2）个向量中。
2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A 的末尾，其时间复杂度应为（O(m)）。
3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(front == NULL)。
4. 若让元素1,2,3依次进栈，则出栈次序不可能出现(3,1,2 )种情况。
5. 图的广度优先搜索类似于树的（层次）遍历。深度优先搜索遍历类似于树的先根遍历
6. 下面程序段的时间复杂度为(O(m*n) )。
for(int i=0; i for(int j=0; j 7. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（模式匹配）。 8 利用双向链表作线性表的存储结构的优点是（便于双向进行插入和删除的操作）。 9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行(s->link=top; top=s;)操作。 10. 一棵具有35个结点的完全二叉树的高度为(6)。假定空树的高度为-1。 11. 一个有n个顶点和n条边的无向图一定是(有回路) 的。 12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（O(n)）。 13. 已知广义表为A((a,b,c),(d,e,f))，从A 中取出原子e的运算是（Head(Head(Tail(Tail(A))))）。 14. 在一棵树的静态双亲表示中，每个存储结点包含( 2)个域。 15. 有向图中的一个顶点的度数等于该顶点的(入度与出度之和)。 15. 与邻接矩阵相比，邻接表更适合于存储(稀疏图)。 17. 较快的数据搜索方法是（折半）搜索方法。 18. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（同义词之间或非同义词之间发生冲突）引起的。 19. 根据n个元素建立一个有序单链表的时间复杂度为（O(n)）。 20. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为(front==rear)。 21. 假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有(6i)个结点。 22. 对于具有e条边的无向图，它的邻接表中共有(2e )个边结点。 23. 图的深度优先搜索遍历类似于树的（先根）次序遍历。 24．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?( C、B、E、D、A、F ) 25．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：( 98 ) 26. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：({5、9、17、21、23、25、30} ) 27．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为(用尾指针表示的单循环链表) 28．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：((F, H, C, D, P, A, M, Q, R, S, Y, X) ) 29．下面是三个关于有向图运算的叙述：(都不正确 ) （1）求有向图结点的拓扑序列，其结果必定是唯一的 （2）求两个指向结点间的最短路径，其结果必定是唯一的 （3）求AOE网的关键路径，其结果必定是唯一的 其中哪个（些）是正确的？ 30．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: (6) 31. 以下关于广义表的叙述中,正确的是：(广义表是由0个或多个单元素或子表构成的有限序列) 32. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？(冒泡排序) 33．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：(将邻接矩阵的第i行元素全部置为0 ) 34．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：(head->next==head) 35. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找关键码值11，所需的关键码比较次数为：( 3 ) 36. 以下哪一个不是队列的基本运算？(从队列中删除第i个元素) 37．对包含n个元素的哈希表进行查找，平均查找长度为：(不直接依赖于n) 38．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：(50) 39．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：( 4 ) 40．下面(存储密度大)是顺序存储结构的优点。 41．下面关于串的叙述中，(空串是由空格构成的串)是不正确的。 42．(无向图)的邻接矩阵是对称矩阵。 43．用链式方式存储的队列，在进行删除运算时，(仅修改头指针)。 44．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是(G)。 先序序列：EFHIGJK 中序序列：HFIEJKG 45．下面(拓朴排序 )方法可以判断出一个有向图中是否有环。 46．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(插入) 排序法。 47．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是 (dceab)。 48．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是（2*i>n）。 49．向一个有128个元素的顺序表中插入一个 新元素并保持原来顺序不变，平均要移动 （64）个元素。 50．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（p->next=q->next; q->nxet=p）。 51．对一个满二叉树，m个树叶，n个结点，深度为h，则有（n=2h-1）。 52．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（选择排序）。 53．用链式方式存储的队列，在进行插入运算时，（仅修改头指针）。 54．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移（n-i+1）个元素。 55．一个栈的入栈序列是12345，则栈的不可能的输出序列是（54132 ）。 56．5个顶点的有向图最多有（20）条弧。 57．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为（front==rear）58．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（单向循环链表）存储方式最省时间。 59．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ 34）。 60. 单循环链表的主要优点是（从表中任一结点出发都能扫描到整个链表）。 61. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（4、3、5、1、2）。 62. 串是一种特殊的线性表，其特殊性表现在（数据元素是多个字符）。 63. n个顶点的无向图中最多有（ n(n-1)/2）条边。 64. 6个顶点的无向图中，至少有（5）条边才能保证是一个连通图。 65．若某线性表中最常用的操作是删除第1个元素，则不宜采用（顺序表）存储方式。 66．在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其右孩子的编号为（2i+1）。 67. 按照二叉树的定义，具有3个结点的二叉树有（5）种不同形态。 68. 在长为n的顺序表中，删除第i个元素(1≤i≤n+1)需要向前移动（n-i ）个元素。 69. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（1、2、3、4、5）。 70. 栈是一种特殊的线性表，其特殊性表现在（只能从端点进行插入和删除）。 71. 一棵二叉树中，第k层上最多有（2k-1）个结点。 72. 一棵有18个结点的二叉树，其高度最小为（ 5 ）层。 73.有向图中，所有顶点入度和是所有顶点出度和的（1）倍。 填空题： 1.数据元素之间存在的相互关系称为结构。 2.数据结构从逻辑上分为线性结构和非线性结构。 3.线性表的顺序存储结构称为顺序表。 4.所有插入在表的一端进行，而所有删除在表的另 一端进行的线性表称为队列。 5.深度为h的二叉树,最少有 h 个结点。 6.折半查找要求待查表为有序表。 7.n个记录按其关键字大小递增或递减的次序排列 起来的过程称为排序。 8.存储数据时,不仅要存储数据元素的信息,还 要存储元素之间的相互关系。 9．将一棵有100个结点的完全二叉树按层编号， 则编号为49的结点X，其双亲PARENT（X）的编号 为24_。 10、一个字符串相等的充要条件是两字符串长度 相同和对应位置上的字符也相同。 11、在有向图的邻接表和逆邻接表表示中，每个顶 点的边链表中分别链接着该顶点的所有和_ 结点。 11、在一个长度为n 的顺序表中向第 i 个元素 （0 动_n-i+1 个元素。 12、队列是只允许在表的一端进行插入，而在另 一端进行删除的线性表。 13、设主串T＝“abxxyxyxxbaa”,模式串P＝“xyxx” 则第 3 次匹配成功。 14、在一棵二叉树中，第5层上的结点数最多为16 。（根的层次为1） 15、假设一个9阶的上三角矩阵A按列优先顺序 压缩存储在一维数组中，其中B［0］存储矩阵中第 1个元素a1,1 ，则B[31] 中存放的元素是_a21 。16、有n个结点的二叉链表中，其中空的指针域为 n+1，指向孩子的指针个数为_ n-1 。 17、二叉树后序遍历的顺序是ABCDE，则该二叉树 的根结点是 E 。 18、对于一个具有n 个顶点和e 条边的无向图， 若采用邻接表表示，则整个邻接表中的结点总数是 _ 4n 。19、在单链表上难以实现的排序方法有_ 选 择性和_ 排序。 20、_ 散列表查找法的平均查找长度与元素个数 n无关。 21、在有n 个元素的顺序表的任意位置插入一个元 素所需移动结点的平均次数为 n/2。 22、栈是插入和删除元素都在表的同一端进行的 线性表。 23、广义表L＝（a,b,c,L）,则其长度为_4。24、在树中，除跟结点外，其他结点都有且只有一个前驱结点。 26、在串s=“structure”中，以t 为首字符的子串有12 个。 27、广度优先搜索遍历类似于树的按层次遍历的过程。 28、已知一棵完全二叉树中共有768个结点为，则该树中共有 384 个叶子结点。 29、在有序表（12,24,36,48,60,72,84）中二分查找关键字72时所需进行的关键字比较次数为2 。 30、两个长度分别m和n（m>n）的排好序的表归并成一个排好序的表，至少要进行_ 次键值比较。通常从四个方面评价算法的质量：正确性、可读性、健壮性和高效性。 。31.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__O(n)_。 3 32.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有____2n_个指针域，其中有_n-1_个指针域是存放了地址，有__n+1__个指针是空指针。n2+1+n2=n n(n-1)/2 33.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有__e_个和_2e_个。 34.在一个具有n个顶点的无向完全图中，包含有_n(n-1)/2_条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)_条边。 31、36.在快速排序、堆排序、归并排序中，___ 归并_排序是稳定的。 32、37.中序遍历二叉排序树所得到的序列是__有 序_序列。 38.快速排序的最坏时间复杂度为__0（n2）_，平均 时间复杂度为___0（nlong2n）__。 39.设一组初始记录关键字序列为(55，63，44，38， 75，80，31，56)，则利用筛选法建立的初始堆为 （31,38，54,56,75,80,55,63）。 40．数据的物理结构主要包括__顺序存储结构_和_ 链式存储结构_两种情况。 41.设一棵完全二叉树中有500个结点，则该二叉 树的深度为__9__；若用二叉链表作为该完全二叉 树的存储结构，则共有__501__个空指针域。 42、设输入序列为1、2、3，则经过栈的作用后可 以得到__5__种不同的输出序列。43、设有向图G 用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵 中第i行上所有元素之和等于顶点i的__出度__， 第i列上所有元素之和等于顶点i的__入度__。设 哈夫曼树中共有n个结点，则该哈夫曼树中有_0_ 个度数为1的结点。 44、设有向图G中有n个顶点e条有向边，所有的 顶点入度数之和为d，则e和d的关系为__e=d_。 45、__中序_遍历二叉排序树中的结点可以得到一 个递增的关键字序列（填先序、中序或后序）。46、设查找表中有100个元素，如果用二分法查找 方法查找数据元素X，则最多需要比较__7__次就可 以断定数据元素X是否在查找表中。 47、不论是顺序存储结构的栈还是链式存储结构 的栈，其入栈和出栈操作的时间复杂度均为 __O(1)___。 48、设有n个结点的完全二叉树，如果按照从自上 到下、从左到右从1开始顺序编号，则第i个结点 的双亲结点编号为_[i/2]_，右孩子结点的编号为 _2i+1__。 49、设一组初始记录关键字为(72，73，71，23， 94，16，5)，则以记录关键字72为基准的一趟快 速排序结果为（5,16,71,23,72,94,73）。 50、设有向图G中有向边的集合E={<1，2>，<2， 3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓 扑序列为（1,4,3,2）。 51、下列算法实现在顺序散列表中查找值为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=(_j+1_) %m; if (i==j) return(-1);} if (_hashtable.key==k__ ) return(j); else return(-1); } j+1，hashtable[j].key==k 52、下列算法实现在二叉排序树上查找关键值k， 请在下划线处填上正确的语句。 typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) { if (t==0 ) return(0);else while (t!=0) if (t->key==k)_retrun(t)_; else if (t->key>k) t=t->lchild; else_t=t->rchild_; } return(t)，t=t->rchild 53、设有n个无序的记录关键字，则直接插入排序 的时间复杂度为_0（n2）_，快速排序的平均时间复 杂度为__0（nlong2n）_。 54、设指针变量p指向双向循环链表中的结点X， 则删除结点X需要执行的语句序列为 __p>1Link->rLink=p->rLink->1Link=p->rLink__ （设结点中的两个指针域分别为llink和rlink）。 根据初始关键字序列(19，22，01，38，10)建立的 二叉排序树的高度为_ 3_。 55、深度为k的完全二叉树中最少有_ 2k-1_个结 点。 56、设初始记录关键字序列为(K1，K2，…，K n)， 则用筛选法思想建堆必须从第_ n/2_个元素开始进 行筛选。 59、设哈夫曼树中共有99个结点，则该树中有_50_ 个叶子结点；若采用二叉链表作为存储结构，则该 树中有_51_个空指针域。 60、设有一个顺序循环队列中有M个存储单元，则 该循环队列中最多能够存储_M-1__个队列元素；当 前实际存储__(R-F+M)%M__个队列元素（设头指针F 指向当前队头元素的前一个位置，尾指针指向当前 队尾元素的位置）。 61、设顺序线性表中有n个数据元素，则第i个位 置上插入一个数据元素需要移动表中_n-i+1__个 数据元素；删除第i个位置上的数据元素需要移动 表中_n-i__个元素。 62、设一组初始记录关键字序列为(20，18，22， 16，30，19)，则以20为中轴的一趟快速排序结果 为(19,18,16,20,30,22)。 63、设一组初始记录关键字序列为(20，18，22， 16，30，19)，则根据这些初始关键字序列建成的 初始堆为(16,18,19,20,30,22)。 64、设无向图对应的邻接矩阵为A，则A中第i上 非0元素的个数__等于__第i列上非0元素的个数 （填等于，大于或小于）。 65、设前序遍历某二叉树的序列为ABCD，中序遍历 该二叉树的序列为BADC，则后序遍历该二叉树的序 列为__BDCA__。 66、设散列函数H(k)=k mod p，解决冲突的方法为 链地址法。要求在下列算法划线处填上正确的语句 完成在散列表hashtalbe中查找关键字值等于k的 结点，成功时返回指向关键字的指针，不成功时返 回标志0。 全国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 页） 全国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．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 全国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 ) 全国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) 全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。 ??????????????????????精品自学考料推荐?????????????????? 全国 2019 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（） A. 逻辑结构、存储结构、机外表示 B. 存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D. 机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 3.下列关于线性表的基本操作中，属于加工型的操作是（） A. 初始化、求表长度、插入操作 B. 初始化、插入、删除操作 C.求表长度、读元素、定位操作 D. 定位、插入、删除操作 4.在一个单链表中，若p 所指结点不是最后结点， s 指向已生成的新结点，则在p 之后插入 s 所指结点的正确操作是（）A.s–>next=p –>next; p –>next=s; C.s–>next=p; p –>next=s; B.p –>next=s –>next; s –>next=p; D.s–>next=p –>next; p=s; 5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（） A.3 种 B.4 种 C.5 种 D.6 种 6.C 语言对数组元素的存放方式通常采用（） A. 按行为主的存储结构 B. 按列为主的存储结构 C.按行或列为主的存储结构 D. 具体存储结构无法确定 7.根据定义，树的叶子结点其度数（） A. 必大于 0 B. 必等于 0 C.必等于 1 D. 必等于 2 8.二叉树若采用二叉链表结构表示，则对于n 个结点的二叉树一定有（） A.2n 个指针域其中n 个指针为 NULL B.2n 个指针域其中n+1 个指针为 NULL C.2n-1 个指针域其中n 个指针为 NULL D.2n-1 个指针域其中n+1 个指针为 NULL 9.在一个无向图中，所有顶点的度数之和等于边数的（） A.1 倍 B.2 倍 C.3 倍 D.4 倍 10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（） 1 第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( ) A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( ) A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( ) A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1) 12.三个顶点v1,v2,v3的图的邻接矩阵为 010 001 010 ?? ?? ?? ?? ?? ，该图中顶点v3的入度为( ) A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找 的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 浙02142# 数据结构导论试题第 2 页共 5 页 2012年10月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。 1.下面几种算法时间复杂度阶数中，值最大的是 A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为 A.正确性 B.易读性 C.健壮性 D.时空性 3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为 A.40 B.60 C.61 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要 ．．．判断栈是否为空的是 A.出栈 B.进栈 C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A C.D，C，B，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是 A.100 B.108 C.114 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5 C.6 D.无法确定 9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1 ： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 第一概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 数据结构导论const maxsize=顺序表的容量； typedf struct {datatype data[maxsize]; int last; {sqlist; sqlist L; 顺序表的插入算法： void insert_sqlist(sqlist L,datetype x,int i) { if(https://www.wendangku.net/doc/a43103621.html,st==maxsize)error(…表潢?)； if((i<1)||(i>https://www.wendangku.net/doc/a43103621.html,st+1))error(…非法位置?)； for(j=https://www.wendangku.net/doc/a43103621.html,st;j=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=X; https://www.wendangku.net/doc/a43103621.html,st=https://www.wendangku.net/doc/a43103621.html,st+1 } 顺序表的删除算法： void delete_sqlist(sqlist L,int i); { if((i<1)||(i>https://www.wendangku.net/doc/a43103621.html,st)) error(非法位置)； for(j=i+1;j=https://www.wendangku.net/doc/a43103621.html,st;j++) L.data[j-2]=L.data[j-1]; https://www.wendangku.net/doc/a43103621.html,st=https://www.wendangku.net/doc/a43103621.html,st-1 } 顺序表的查找算法： int locate_sqlist(sqlist L,datatype X) { i=1; while((i<=https://www.wendangku.net/doc/a43103621.html,st)&&(L.data[i-1]!=x)) i++; if(i<=https://www.wendangku.net/doc/a43103621.html,st) return(i) else return(0) } 单链表类型定义 typedef struct node *pointer; struct node {datatype data; pointer next; }; typedef pointer lklist; 实践考核题第一题设计报告书 学生姓名学生学号 所在地区泰安市提交日期（年/月）2014/6 实践题目利用队的结构解决实际问题 需求分析 (1)、置空 setnull ( queue ) 将队列 queue 置成空队列 调用setnull(queue)函数把队列queue的顶端指针和低端指针指向同一块地址，这样就把队列置空。当队列中的数据元素不用或者必须要清楚的时候，就必须调用该函数把队列中的数据清空才能在插入新的数据供用户操作使用。 (2)、入队 enqueue ( queue ， x ) 将元素 x 插入队列 queue 的尾部 调用函数enqueue(queue,x),通过移动首指针找到要入队的数据，直到把队列的空间占满。有 数据要进入队列时，调用该函数把数据元素x插入到队列中，先判断队列是否已满让后才能把数据元素插入到队尾。 (3)、出队 dequeue ( queue ) 删除队列 queue 的队头元素，函数返回被删除元素的值 通过移动首指针把队首的指针往下移动一个地址，这样就把一个元素数据出队了。当要出队时，队列是从头指针开始一系列操作。先判断该队列是否为空队列，如果不是的话，在进行出队操作把头指针往上移一个地址，这样就把数据出队了。 （4）、判队空isempty ( queue ) 若栈stack 为空，函数返回0 ，否则返回1 判断队列的为空的条件是（queue.rear==queue.front）如果为空返回数值1，否则返回0。当出队操作时，需要判断队列是否为空，调用该函数。 概要设计 这三个函数置空、入队和出队，使用的都是顺序循环存储结构。 队列是有限个同类型数据元素的线性序列，是一种先进先出（First In First Out）的新型表，新加入的数据元素插在队列的尾端，出队列的数据元素在队列首部被删除。 顺序存储实现的队列称为顺序队列，它由一个一维数组（用于存储队列中元素）及两个分别指示队列首和队列尾元素的变量组成，这两个变量分别称为“队列首指针”和“队列尾指针”。 （1）、队列是有限的数据元素的集合，要定义一个常量说明该队列的大小； （2）、定义顺序队列的类型包括一个数据域和两个指针域（首指针和尾指针），并声明一个该类型的变量以便于操作； （3）、根据需求分析写出每个函数的功能： 置空函数：根据函数的形参，即传递进来的队列指针，调用它的首指针和尾指针让两个指针相等，就把队列中的元素全部清空。 入队函数：首先判断该队列是否已满，如果队列已满，就退出操作。否则，执行入队操作的语句，由于是循环队列所以在移动尾指针时，要把尾指针的位置取余运算（queue.rear=(queue.rear+1)%maxsize;），然后把数据元素赋给尾指针(queue,data[queue.rear]=x;)。 出队函数：当有数据元素要出队时，首先判断该队列是否为空，如果为空时，元素出队列失败。否则，当队列不为空时，执行出队操作（queue.front=(queue.front+1)%maxsize;）返回数值1，说明出队成功。判空函数：该函数是用来判断队列是否为空的，是被别的函数调用作为判断条件用，若果为空的话就返回数值0，标志不能继续执行下面的语句。判断为空的条件是：queue.rear==queue.front；如果为空返回值为1，否则返回值为0。 详细设计 对于队列的操作首先需要把队列置空，然后插入数据元素，在插入元素时需要判断是否队列已满，在数据元素出队时需要先对队列判断是否为空，如果为空时结束程序继续执行，否则继续执行出队操作。（1）定义结构体 Typedef struct seqqueue //定义结构体类型seqqueue 我想在自考将要来临之际,为各位正在忙碌复习当中的自考学友们,提供一点复习思路,以便能顺利通过10月份的考试.下面就是我的一点复习心得和总结,希望能对你有所帮助! "如果你想通过数据结构导论这门课,至少得看两遍书吧?" 第一遍就是粗略的看一下,这样你心里也就有了底,也就大概的了解了数据结构导论 这门课所讲的内容,并且那里是考点在头脑里也就都有了大致的把握,这样,你就可以带着相应的重点,去重点把握你觉得重要的东西了!不过其实你到现在如果连一遍也没看过呢,也没关系,我下面的总结就是希望能对这些还没看过书的人,有所帮助! 下面就列出一些我觉得是重点的东西: 1,线性表,这一章整个都比较重要,因为这一章中关于线性表的顺序实现和链接实现及在上面的基本运算,在最后考试中很有可能以多种形式的考法出现(如:选择,填空,应用及程序设计等).并且由于这一章是整本书的基础,所以考试时占的比重会比较大,最后的程序设计题很可能就从这一章里出一道甚至两道都从这章里出(一道程序设计题6分).这一点是我在作过大量模拟试题和分析了历年试卷的基础上得出的结论,应当比较有参考价值.在这一章中有一个知识点应引起大家的注意,就是链式存储结构,因为这种存储结构在以后的各章中对于各种结构的实现(如:树,图等)都比较有用且实用.所以对于它的掌握应当达到"综合应用"的等级!(一点建议:如果你在第一次看的时候遇到了自己不懂的问题,可以先尝试着跳过去看后面的,等后面的看完了,再回过头看不会的这一段,问题就可能迎刃而解了!^>,中国水利水电出版社,宁郑元主编一书)只要知道它的各种运算及结果就可以了(考试时也就这么考了:--P) 如:DELETE ("ACABA",3,3)=? 结果为:"AC" 又如:SUBSTR("ABBCA",2,2)=? 结果为:"BB" 2,栈,队列和数组:这一章里你要掌握的东西就比较简单了(如果你掌握了上一章的内容对于这一章来讲,基本上就没有难题了)这一章里你要牢记两个概念:关于栈和队列的修改原则:(1),栈,后进先出,所有操作都是在栈顶进行的.(2),队列,先进先出,插入运算只能在对尾进行,删除运算只能在对头进行!且注意对头指针指示对头元素在数组中实际位置的前一个位置;实现递归调用属于栈的应用! 再附上关于栈和队列的几道例题如下: 1,运算(*作)是数据结构的一个重要方面,试举一例,说明两个数据结构的.逻辑结构和存储方式完全相同,只是对于运算(*作)的定义不同,因而两个结构具有显著不同的特性,是两个不同的结构. 全国2018年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的四种基本逻辑结构是指( ) A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性 C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性 3.下列关于线性表的叙述中，不正确的是( ) A.线性表是n个结点的有穷序列 B.线性表可以为空表 C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系 4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( ) A.p=p->next B.p->next=p->next C.p->next=p->next->next D.p->next=p 5.栈和队列( ) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处 6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( ) A.127 B.142 C.150 D.157 7.深度为k的二叉树至多有( ) A.2k个结点 B.2k-1个结点 C.2k-1个结点 D.2k-1-1个结点 8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( ) A.ABCDEF B.ABECDF C.CDFBEA D.CBDAEF 1 第一章概论 1，数据表示：将数据从机外表示转化为机内表示。变化过程：机外表示->逻辑结构->存储结构。 2，数据处理：计算机执行对机内表示的数据的各种操作从而实现处理要求，得到所需结果。 过程：处理要求->基本运算和运算->算法 3，计算机专业人员的两项基本任务：数据表示和数据处理。 4，从数据结构观点看，通常的数据分为三个层次：数据、数据元素、数据项。 5，凡能被计算机存储、加工的对象通称为数据。 6，数据元素是数据的基本单位，具有完整确定的实际意义，又称为元素，结点，顶点或记录。 7，数据项是数据的不可分割的最小单位，不具备完整确定的实际意义，又称字段、域。数据元素由数据项组成。8，逻辑关系是指数据元素之间的关联方式或称邻接关系 9，数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。 10，数据逻辑结构四种基本形式：集合、线性结构、树形结构、图状结构。 11，集合：任何两个结点之间都没有逻辑关系，组织形式松散。 12，线性结构：结点按逻辑关系依次排列成一条锁链。 13，树形结构：具有分支、层次特点，其形态类似自然界中的树。 14，图状结构：各个结点按逻辑关系相互缠绕，任何两个结点都可以邻接。 15逻辑结构与数据元素本身形式、内容无关。逻辑结构与数据元素相对位置无关。逻辑结构与结点个数无关。 16，在数据的逻辑结构上规定的某种操作称为运算。运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象，以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。 17，运算两种基本类型：加工型运算和引用型运算。查找：找出满足某条件的结点在逻辑结构中的位置。 读取：读出某逻辑结构中指定位置的结点的内容。插入：在某逻辑结构中指定位置增加一个新结点。 删除：撤销某逻辑结构中指定位置的结点。更新：修改某逻辑结构中指定位置的结点内容。 18，数据结构中将数据的组织形式（逻辑结构）和对数据的操作方式（基本运算）作为一个整体来看待。 19，存储实现的目的是建立数据的机内表示。建立的数据的机内表示称为数据的存储结构。 20，一个存储结构分为三个部分：存储节点，数据元素之间的关联方式，附加设施。 21，四种基本存储结构：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。（理解四种形式） 22，算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。一个算法规定了求解给定问题所需要的所有处理步骤及其执行顺序，使得给定类型的任何问题都能在有限时间内被机械的求解。 23，任何算法都是用某种语言加以描述的。三类：程序（计算机语言描述算法），伪语言算法，非形式算法。 24，非形式算法：用自然语言同时可能还使用了程序设计语言或伪语言描述的算法。 25，评价算法的4个方面：正确性，易读性，健壮性，高效性。高效性是指算法的时间性能和空间性能。自考数据结构导论20051年10月试卷
全国自学考试数据结构导论试题及答案(4套)
02142数据结构导论201604
自考数据结构导论复习资料
自考数据结构导论
全国数据结构导论10月高等教育自学考试试题与答案
2010年1月自考数据结构导论真题
2020年10月全国数据结构导论自考试题及答案解析.doc
自考02142《数据结构导论》串讲笔记
自考数据结构导论20120年01月试卷
02142数据结构导论份真题及答案.doc
自考02142《数据结构导论》串讲笔记
自考02142《大数据结构导论》串讲笔记
数据结构导论
数据结构导论-实践设计报告-1
“数据结构导论”的学习方法
1月全国自考数据结构导论试题及答案解析
数据结构导论2142复习资料
- 数据结构导论
- 自考数据结构导论
- “数据结构导论”的学习方法
- 全国自学考试数据结构导论试题及答案(4套)
- 复习资料(数据结构导论)
- 数据结构导论作业一
- 02142数据结构导论份真题及答案.doc
- 数据结构导论2142复习资料
- 数据结构导论知识点
- 数据结构导论“ 图”
- 02142数据结构导论2016年10月份真题及答案
- 数据结构导论-实践设计报告-1
- 全国自学考试数据结构导论试题及答案(4套)
- 数据结构导论选择
- 2014年4月自考数据结构导论试题及答案
- 自考02142《数据结构导论》串讲笔记
- 02142数据结构导论2012年10月份真题及答案
- 02142数据结构导论201610
- 02142数据结构导论201710月份真题答案与解析
- 自考数据结构导论复习资料