全国2007年1月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．关于栈和队列的说法中正确的是（）
A．栈和队列都是线性结构
B.栈是线性结构，队列不是线性结构
C.栈不是线性结构，队列是线性结构
D.栈和队列都不是线性结构
2．关于存储相同数据元素的说法中正确的是（）
A．顺序存储比链式存储少占空间
B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间
D.链式存储比顺序存储难于扩充空间
3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）
A．线性结构 B.树形结构
C.线性结构和树型结构
D.线性结构和图状结构
4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）
A．q→next=s；p→next=s； B.q→next=s；s→next=p；
C.q→next=s；q→next=p；
D.q→next=s；s→next=q；
5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）
A．O(n) B.O(1)
C.O(log2n)
D.O(n2)
6．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A．a，b，c，d B.a，b，d，c
C.d，c，b，a
D.c，d，a，b
7．关于串的叙述中，正确的是（）
A．空串是只含有零个字符的串
B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串
D.串是含有一个或多个字符的有穷序列
8．在具有m 个单元的循环队列中，队头指针为front ，队尾指针为rear ，则队满的条件是（ ） A ．front==rear B.(front+1)%m==rear C.rear+1==front
D.(rear+1)%m==front
9．设有二维数组A ［n ］［n ］表示如下：?????
??????
? 6
53
421， 则A ［i ］［i ］（0≤i ≤n-1）的值为（ ）
A ．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2
D.i 2
/2
10．高度为h 的完全二叉树中，结点数最多为（ ） A ．2h-1 B.2h+1 C.2h
-1
D.2h
11．由m 棵结点数为n 的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数
是（ ） A ．mn B.mn-1 C.n(m-1)
D.m(n-1)
12．在一个具有n 个顶点的无向图中，每个顶点度的最大值为（ ） A ．n B.n-1 C.n+1
D.2(n-1)
13．关于无向图的邻接矩阵的说法中正确的是（ ） A ．矩阵中非全零元素的行数等于图中的顶点数 B.第i 行上与第i 列上非零元素总和等于顶点V i 的度数 C.矩阵中的非零元素个数等于图的边数
D.第i 行上非零元素个数和第i 列上非零元素个数一定相等
14．设一组记录的关键字key 值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它
的开散列表中散列地址为1的链中的结点个数是（ ） A ．1 B.2 Ｃ．3
D.4
15．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准
得到的一次划分为（ ） A ．36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88
D.44，36，49，55，88，81
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_______。
17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。
18．在顺序表上读表元算法的时间复杂度为_______。
19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;_______;
20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］的存储位置为_______。
21．有4个结点且深度为4的二叉树的形态共有_______种。
22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。
24．一个具有10个顶点的完全无向图中有_______条边。
25．一棵平衡二叉树中任一结点的平衡因子只可能是_______。
26．二分查找的时间复杂度为_______。
27．二路归并排序算法的时间复杂度为_______。
28．文件的基本存取单位是_______。
三、应用题(本大题共5小题，每小题6分，共30分)
29．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。
30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。
31．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出整个冒泡排序的每一趟过程。32．题32图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。
题32图
33．已知连通网的邻接矩阵A=
???????
????????
?∞∞
∞∞∞∞∞∞∞4
2
104962812981106121， 试画出它所表示的连通网并画出该连通网的最小生成树。
四、算法设计题(本大题共2小题，每小题7分，共14分) 34．设单链表的结点结构如下：
struct node{datatype data;
struct node*next; }
试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x 的结点个数。
35．试写出直接插入排序算法。
全国2007年10月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.在数据结构中，从逻辑上可以把数据结构分成( ) A.线性结构和非线性结构 B.紧凑结构和非紧凑结构 C.动态结构和静态结构 D.内部结构和外部结构
2.for （i=0；i for （j=0；j A ［i ］［j ］=i*j ； 上面算法的时间复杂度为( ) A.O(m 2) B.O(n 2) C.O(m ×n) D.O(m+n ） 3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9 4.设p 为指向双向循环链表中某个结点的指针，p 所指向的结点的两个链域分别用p →llink 和p →rlink 表示，则同样表示p 指针所指向结点的表达式是( ) A.p →llink B.p →rlink C.p →llink →llink D.p →llink →rlink 5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( ) A. 110 B. 108 C. 100 D. 120 6.设有一个栈，按A 、B 、C 、D 的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB 7.在一个具有n 个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top 为栈顶指针，则当做出栈处理时，top 变化为( ) A.top++ B.top-- C.top 不变 D.top=0 8.除根结点外，树上每个结点( ) A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( ) A.2 B.3 C.5 D.8 题9图 10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20 11.设图的邻接矩阵为??? ? ? ? ?01 0100 110 ，则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图 12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表 13. 用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于 解决上述问题的是( ) A.线性探测法 B.除留余数法 C.平方取中法 D.折叠法 14.排序算法中，第一趟排序后，任一元素都不能 ．．．确定其最终位置的算法是( ) A.选择排序 B.插入排序 C.冒泡排序 D.快速排序 15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( ) A.希尔排序 B.归并排序 C.插入排序 D.选择排序 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为__________型运算。 17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__________”。 18.单链表中逻辑上相邻的两个元素在物理位置上__________相邻。 19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是__________。 20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。 21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。Array 题21图 22.具有n个顶点的连通图至少需有__________条边。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。 24.设顺序表的表长为n ，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。 25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。 26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是__________存取、直接存取和按关键字存取。 27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行__________趟才能够完成。 28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为__________。 三、应用题(本大题共5小题，每小题6分，共30分) 29.分别写出题29图中二叉树的先根、中根、后根遍历序列。 题29图 30.设要将序列（Q ，H ，C ，Y ，P ，A ，M ，S ，R ）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 31.如题31图所示，输入元素为A ，B ，C ，在栈的输出端得到一个输出序列ABC ，试写出在栈的输入端三个可能的输入序列。 题31图 32.已知无向图G 的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。 题32图 33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示： 题34图 struct node{ int info;struct node *link; } int Delete (struct node *head, int x) { struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/ if (! head ) return (0); if (head→link ==head) { if (head→info==x) { free (head);head=NULL；return (x) } return (0); } p=head; q=head; while (q→link!=head) q=(1) ; while (p→link!=head) { if (p→info==x) { (2) ; if (p==head) head=(3) ; free (p);return (x); } else { q=p ;（4）;} } return (0); } 35.设以二叉链表为二叉树的存储结构，结点的结构如下： 其中data域为整数，试设计一个算法void change(bitreptr r): 若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。 全国2008年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在数据结构中，数据的基本单位是( ) A. 数据项 B. 数据元素 C. 数据对象 D. 数据文件 2.k=1; for（i=0；i for（j=0；j A［i］［j］=k++； 上述程序段的时间复杂度为( ) A.O（n2） B.O（n） C.O（2n） D.O（1） 3.线性表采用链式存储结构时，要求内存中可用存储单元的地址( ) A. 必须是连续的 B. 必须是部分连续的 C. 一定是不连续的 D. 连续和不连续都可以 4.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段 p=h; while (p->next->next!=h) p=p->next; p->next=h; 后（其中，p->next为p指向结点的指针域），则( ) A. p->next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点 5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245 6.一个栈的入栈序列是a ，b ，c ，d ，e ，则栈的输出序列不可能．．．是( ) A. dceab B. decba C. edcba D. abcde 7.元素大小为1个单元，容量为n 个单元的非空顺序栈中，以地址高端为栈底，以top 作为栈顶指针，则出栈处理后，top 的值应修改为( ) A. top=top B. top=n-1 C. top=top-1 D. top=top+1 8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( ) A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点 9.在完全二叉树中，若一个结点是叶结点，则它没有( ) A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点 10.邻接矩阵为对称矩阵的图是( ) A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图 11.在一个具有n 个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D. 2 n 12.若构造一棵具有n 个结点的二叉排序树，最坏的情况下其深度不超过( ) A. 2 n B. n C. 2 1n D. n+1 13.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的 14.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是( ) A. 快速排序 B. 堆排序 C. 插入排序 D. 二路归并排序 15.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( ) A.希尔排序 B.插入排序 C.冒泡排序 D.快速排序得分 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。 17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“____________”。 18.对稀疏矩阵进行压缩存储的目的是节省____________。 19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____________。 20.深度为15的满二叉树上，第11层有____________个结点。 21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为____________。 22.一个具有4个顶点的无向完全图有____________条边。 23.一个有向图G中若有孤 24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。 25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。 26.文件的检索有三种方式，它们是顺序存取、直接存取和____________存取。 27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用____________。 28.对n个元素的序列进行冒泡排序时，最多需进行____________趟。 三、应用题(本大题共5小题，每小题6分，共30分) 29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的结 果。 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。 31.设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求： （1）构造散列表； （2）求查找数34需要比较的次数。 32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA 及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 题32图 33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。 题33图 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.编写一个函数void insert(int *p,int size,int a)，其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是：首先采用折半查找的方法，找出要插入数据的位置；然后按升序将数据插入该数组中。 35.某带头结点的单链表的结点结构说明如下： typedef struct node1 { int data; struct node1 *next }node； 试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。 全国2008年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.从逻辑上可以把数据结构分为（） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确 ．．．的是（） A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（） A.直接前趋 B.直接后继 C.开始结点 D.终端结点 4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（） A.n B.2n-1 C.2n D.n2 5.栈和队列共同具有的特点是（） A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（） A.1和5 B.2和4 C.4和2 D.5和1 7.数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A ［5］［5］的地址是（） A.1175 B.1180 C.1205 D.1210 8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（） A.n-1 B.n C.n+1 D.n+2 9.在一棵深度为H的完全二叉树中，所含结点的个数不少于 ．．．（） A.2H-1-1 B.2H-1 C.2H-1 D.2H 10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（） A.0 B.1 C.n D.不确定 11.下列说法中不正确 ．．．的是（） A.无向图的极大连通子图称为连通分量 B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法 12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（） A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列 13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（） A.1 B.2 C.4 D.8 14.一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（） A.80，45，55，40，42，85 B.85，80，55，40，42，45 C.85，80，55，45，42，40 D.85，55，80，42，45，40 15.关于VSAM文件存取操作的说法，正确的是（） A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取 C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取 二、填空题（本大题共13小题，每小题2分，共26分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为 ________。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、________和散列存储方式。 18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动________个元素。 19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为________。 20.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作 串为________。 21.具有n个叶子结点的哈夫曼树，其结点总数为________。 22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于________。 24.两个串是相等的，当且仅当两个串的长度相等且________的字符都相同。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。 26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为________。 27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。 28.对n个元素进行冒泡排序时，最少的比较次数为________。 三、应用题（本大题共5小题，每小题6分，共30分） 29.设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。 30.画出题30图所示的二叉树的二叉链表存储结构。 题30图 31.对于题31图，试给出： （2）邻接表。 题31图 32.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 33.用插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行排序，写出整个插入排序的每一趟过程。 四、算法设计题（本大题共2小题，每小题7分，共14分） 34.设两个数据元素均为整型数据的线性表A=（a1，a2，…，a n）和B=（b1，b2，…，b m）。若n=m且a i=b i（i=1，2,…，n）则认为A=B；若a i=b i（i=1，2,…，j）且a j+1B。试编写一个比较A和B的算法，当A 构使用链接存储。 35.设二叉树的结点类型定义如下： typedef struct node{ datatype data; struct node*lchild,*rchild; }Bitree; Bitree*t; 试编写一个计算二叉树深度的递归算法（int Depth（Bitree*t））。 全国2009年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的不可分割的最小标识单位是（） A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i for（j=0；j c［i］［j］=0； for（i=0；i for（j=0；j for（k=0；k c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为（） A.O（m+n×t） B.O（m+n+t） C.O（m×n×t） D.O（m×t+n） 3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（） A.单链表 B.双链表 C.单循环链表 D.顺序表 4.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（） A.p—>next=p—>next—>next B.p=p—>next C.p=p—>next—>next D.p—>next=p 5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（） A.hs—>next=s； B.s—>next=hs；hs=s； C.s—>next=hs—>next；hs—>next=s； D.s—>next=hs；hs=hs—>next； 6.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾 元素。如果队列中元素的个数为11，front 的值为25，则rear 应指向的元素是（ ） A.Q ［4］ B.Q ［5］ C.Q ［14］ D.Q ［15］ 7.定义二维数组A ［1‥8，0‥10］，起始地址为LOC ，每个元素占2L 个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L ，则在以列序为主序的存储方式下，该元素的存储地址为（ ） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L 8.具有n 个结点的二叉树，拥有指向孩子结点的分支数目是（ ） A.n-1 B.n C.n+1 D.2n 9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ） A.99 B.98 C.97 D.50 10.有m 个叶子结点的哈夫曼树，其结点总数是（ ） A.2m-1 B.2m C.2m+1 D.2（m+1） 11.有n 个结点的无向图的边数最多为（ ） A.n+1 B.2 1)-n(n C.n （n+1） D.2n （n+1） 12.设图的邻接矩阵为??? ? ? ?????01 100 110 ，则该图为（ ） A.有向图 B.无向图 C.强连通图 D.完全图 13.二分查找算法的时间复杂度是（ ） A.O （n 2） B.O （nlog 2n ） C.O （n ） D.O （log 2n ） 14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） A.4 B.5 C.6 D.7 15.采用排序算法对n 个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ） A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡 二、填空题（本大题共13小题，每小题2分，共26分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。 17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_________。 18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 _________和 _________。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_________和_________。 20.在栈结构中，允许插入的一端称为_________；在队列结构中，允许插入的一端称为_________。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_________。 22.深度为k的二叉树至多有_________个结点，最少有_________个结点。 23.设有一稠密图G，则G采用_________存储结构较省空间。设有一稀疏图G，则G采用_________存储结构较省空间。 24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_________个元素结点。 25.假定对线性表R［0…59］进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。 26.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中_________特别适应磁带存储器，也适应磁盘存储器。 27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是_________。 28.冒泡排序最好的时间复杂度为_________，平均时间复杂度为_________，是一种稳定的排序算法。 三、应用题（本大题共5小题，每小题6分，共30分） 29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。 30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。 题30图 31.已知某图的邻接表存储结构如题31图所示： 题31图 （1）画出该图。 （2）根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。 32.假定采用H（k）=k mod7计算散列地址，引用线性探测的开放定址法解决冲突，试在0~6的散列地址空间中， 对关键字序列（38，25，74，63，52，48）构造散列表，并求出等概率情况下查找成功的平均查找长度。 33.用快速排序法对数据序列（49，38，65，97，16，53，134，27，39）进行排序，写出其第一趟排序的全过程。 四、算法设计题（本大题共2小题，每小题7分，共14分） 34.完善下列折半插入排序算法。 V oid binasort（struct node r［MAXSIZE］，int n） {for（i=2；i<=n；i++）{ r［0］=r［i］；low=1；high=i-1； while（low<=high）{ mid=（1）_________； if（r［0］.key high=（2）_________； else low=（3）_________； } for（j=i-1；j>=low；j- -） （4）_________； r［low］=r［0］； } } 35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。 V oid level（BSTree root，p） { int level=0； if（！root） （1）_________； else{ level++； while（root—>key!=p—>key）{ if（root—>key （2）_________ ； else （3）_________ ； level++； } （4）_________； } } 全国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={ 二00一年下半年全国高等教育自学考试 数据结构导论试卷 一、单项选择题 1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（） A．n B.n/2 C.(n-1)/2 D.(n+1)/2 3．研究数据结构就是研究（） A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构,存储结构及其数据在运算上的实现 4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（） A、1208 B、1212 C、1368 D、1364 6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。 A、13 B、12 C、26 D、25 7．下列几种结构中属于树型结构的是（） 8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（） A、G’为G的连通分量 B、G’为G的无环子图 C、G’为G的子图 D、G’为G的极小连通子图且V’=V 9．下列说法中不正确的是（） A、无向图的极大连通子图称为连通分量 B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D、有向图的遍历不可采用广度优先搜索方法 10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（） A、1次 B、2次 C、3次 D、4次 11．散列表的平均查找长度（） A、与处理冲突方法有关而与表的长度无关 B、与处理冲突方法无关而与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关 12．对ISAM文件的删除记录时，一般（） A、只需做删除标志 B、需移动记录 C、需改变指针 D、一旦删除就需做整理 13．顺序文件适宜于（） A、直接存取 B、成批处理 C、按关键字存取 D、随机存取 14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。 A、快速排序 B、堆排序 C、插入排序 D、二路归并排序 数据结构导论复习 第一章概论 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 绝密★考试结束前 全国2018年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂二写在答题纸上三 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称二姓名二准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上三 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑三如需改动,用橡皮擦干净后,再选涂其他答案标号三不能答在试题卷上三 一二单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸”的相应代码涂黑三错涂二多涂或未涂均无分三 1.数据的逻辑结构分为四种,其中结构最复杂的是 A.集合 B.线性结构 C.树形结构 D.图结构 2.下面程序是矩阵转置算法MM的实现过程,其时间复杂度为 const int n=3; void MM(int A[n][n]) { int i,j,temp; for(i=0;i 3.设顺序表的表长为n,则删除一个元素在最坏情况下元素移动次数为 A.n-2 B.n-1 C.n D.n+1 4.带头结点的双向循环链表L为空的条件是 A.L->next==L->prior B.L->prior==NULL C.(L->next==L)&&(L->prior==L) D.(L->next==L)&&(L->prior=NULL) 5.执行进栈操作,在元素x进栈前需要进行的操作是 A.判断栈是否满,若栈未满,top值加1 B.判断栈是否空,若栈未空,top值加1 C.判断栈是否满,若栈未满,top值减1 D.判断栈是否空,若栈未空,top值减1 6.关于队列,下列叙述正确的是 A.队列的元素个数可以无穷大 B.队列中元素的类型可以不同 C.队列是一个非线性的序列 D.队列的特点是先进先出 7.设循环队列的元素存放在一维数组Q[30]中,队列非空时,front指示队列首结点的前一个位置,rear指示队列尾结点三如果队列中元素的个数为10,front的值为25,则rear应指向的元素是 A.Q[4] B.Q[5] C.Q[14] D.Q[15] 8.二叉树第i(i≥1)层上的结点数最多为 A.2i-1 B.i-1 C.2*i D.2*(i-1) 9.关于二叉链表,下列叙述正确的是 A.二叉链表是二叉树唯一的链式存储结构 B.对二叉链表的访问可以从任意结点开始 C.每个二叉链表不需要有一个指向根节点的指针 D.二叉链表的结点结构包含一个数据域和两个指针域 10.假设初始森林中共有n棵二叉树,每棵树中都仅有一个孤立的结点三将该森林构造成哈夫 曼树,则最终求得的哈夫曼树的结点数为 A.n-1 B.n C.2n-1 D.2n 11.无向图中的极大连通子图是 A.连通分量 B.生成树 C.强连通分量 D.强连通图 12.在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为 A.O(n) B.O(n+e) C.O(n2) D.O(n3) ： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 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.doczj.com/doc/962621475.html,st==maxsize)error(…表潢?)； if((i<1)||(i>https://www.doczj.com/doc/962621475.html,st+1))error(…非法位置?)； for(j=https://www.doczj.com/doc/962621475.html,st;j=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=X; https://www.doczj.com/doc/962621475.html,st=https://www.doczj.com/doc/962621475.html,st+1 } 顺序表的删除算法： void delete_sqlist(sqlist L,int i); { if((i<1)||(i>https://www.doczj.com/doc/962621475.html,st)) error(非法位置)； for(j=i+1;j=https://www.doczj.com/doc/962621475.html,st;j++) L.data[j-2]=L.data[j-1]; https://www.doczj.com/doc/962621475.html,st=https://www.doczj.com/doc/962621475.html,st-1 } 顺序表的查找算法： int locate_sqlist(sqlist L,datatype X) { i=1; while((i<=https://www.doczj.com/doc/962621475.html,st)&&(L.data[i-1]!=x)) i++; if(i<=https://www.doczj.com/doc/962621475.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 2004----01 16下列程序段的时间复杂性量级是____0(n*i)_________。 for (i=1;i 我想在自考将要来临之际,为各位正在忙碌复习当中的自考学友们,提供一点复习思路,以便能顺利通过10月份的考试.下面就是我的一点复习心得和总结,希望能对你有所帮助! "如果你想通过数据结构导论这门课,至少得看两遍书吧?" 第一遍就是粗略的看一下,这样你心里也就有了底,也就大概的了解了数据结构导论 这门课所讲的内容,并且那里是考点在头脑里也就都有了大致的把握,这样,你就可以带着相应的重点,去重点把握你觉得重要的东西了!不过其实你到现在如果连一遍也没看过呢,也没关系,我下面的总结就是希望能对这些还没看过书的人,有所帮助! 下面就列出一些我觉得是重点的东西: 1,线性表,这一章整个都比较重要,因为这一章中关于线性表的顺序实现和链接实现及在上面的基本运算,在最后考试中很有可能以多种形式的考法出现(如:选择,填空,应用及程序设计等).并且由于这一章是整本书的基础,所以考试时占的比重会比较大,最后的程序设计题很可能就从这一章里出一道甚至两道都从这章里出(一道程序设计题6分).这一点是我在作过大量模拟试题和分析了历年试卷的基础上得出的结论,应当比较有参考价值.在这一章中有一个知识点应引起大家的注意,就是链式存储结构,因为这种存储结构在以后的各章中对于各种结构的实现(如:树,图等)都比较有用且实用.所以对于它的掌握应当达到"综合应用"的等级!(一点建议:如果你在第一次看的时候遇到了自己不懂的问题,可以先尝试着跳过去看后面的,等后面的看完了,再回过头看不会的这一段,问题就可能迎刃而解了!^>,中国水利水电出版社,宁郑元主编一书)只要知道它的各种运算及结果就可以了(考试时也就这么考了:--P) 如:DELETE ("ACABA",3,3)=? 结果为:"AC" 又如:SUBSTR("ABBCA",2,2)=? 结果为:"BB" 2,栈,队列和数组:这一章里你要掌握的东西就比较简单了(如果你掌握了上一章的内容对于这一章来讲,基本上就没有难题了)这一章里你要牢记两个概念:关于栈和队列的修改原则:(1),栈,后进先出,所有操作都是在栈顶进行的.(2),队列,先进先出,插入运算只能在对尾进行,删除运算只能在对头进行!且注意对头指针指示对头元素在数组中实际位置的前一个位置;实现递归调用属于栈的应用! 再附上关于栈和队列的几道例题如下: 1,运算(*作)是数据结构的一个重要方面,试举一例,说明两个数据结构的.逻辑结构和存储方式完全相同,只是对于运算(*作)的定义不同,因而两个结构具有显著不同的特性,是两个不同的结构.自考数据结构导论20051年10月试卷
全国自学考试数据结构导论试题及答案(4套)
数据结构导论年月试题
自考数据结构导论复习资料
自考数据结构导论
全国数据结构导论10月高等教育自学考试试题与答案
2010年1月自考数据结构导论真题
2020年10月全国数据结构导论自考试题及答案解析.doc
自考02142《数据结构导论》串讲笔记
自考数据结构导论20120年01月试卷
02142数据结构导论份真题及答案.doc
【自考真题】2018年4月数据结构导论02142试题
自考02142《数据结构导论》串讲笔记
自考02142《大数据结构导论》串讲笔记
数据结构导论
数据结构导论-实践设计报告-1
数据结构导论填空题目汇总
“数据结构导论”的学习方法
相关主题
文本预览