数据结构导论历年真题Word格式文档下载.docx

1、next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点 5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（ ）A.236 B.239 C.242 D.2456.一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是（ ）A. dceab B. decba C. edcba D. abcde7.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为（ ）A. top=top B. top=n-1 C. top=top-1 D. top

2、=top+18.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是（ ）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. 12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过

3、（ ）A. B. n C. D. n+113.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是（ ）A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的14.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是（ ）A. 快速排序 B. 堆排序 C. 插入排序 D. 二路归并排序15.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）A.希尔排序 B.插入排序 C.冒泡排序 D.快速排序得分二

4、、填空题（本大题共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个顶

5、点的无向完全图有_条边。23.一个有向图G中若有孤、和，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为_。24.在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_的。26.文件的检索有三种方式，它们是顺序存取、直接存取和_存取。27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用_。28.对n个元素的序列进行冒泡排序时，最多需进行_趟。三、应用题（本大题共5小题，每小题6分，共30分）29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的

6、结果。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图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中ni

7、l表示空。题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为头指

8、针的单链表复制到一个不带头结点且以head2为头指针的单链表中。全国2007年1月高等教育自学考试数据结构导论试题1关于栈和队列的说法中正确的是（ ）A栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构2关于存储相同数据元素的说法中正确的是（ ）A顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间3从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ）A线性结构 B.树形结构C.线性结构和树型结构 D.线性结构和图状结构4已知一个单链

9、表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ）Aqnext=s；pnext=s； B.qnext=s；snext=p；C.qnext=s；qnext=p； D.qnext=s；snext=q；5在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ）AO（n） B.O（1）C.O（log2n） D.O（n2）6设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ）Aa，b，c，d B.a，b，d，cC.d，c，b，a D.c，d，a，b7关于串的叙述中，正确的是（ ）A空串是只含有零个字

10、符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列8在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）Afront=rear B.（front+1）%m=rearC.rear+1=front D.（rear+1）%m=front9设有二维数组Ann表示如下：， 则Aii（0in-1）的值为（ ）Ai*（i-1）/2 B.i*（i+1）/2C.（i+2）*（i+1）/2 D.i2/210高度为h的完全二叉树中，结点数最多为（ ）A2h-1 B.2h+1C.2h-1 D.2h11由m棵结点数为n的树

11、组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（ ）Amn B.mn-1C.n（m-1） D.m（n-1）12在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ）An B.n-1C.n+1 D.2（n-1）13关于无向图的邻接矩阵的说法中正确的是（ ）A矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等14设一组记录的关键字key值为62，50，14，28，19，35，47，56，83，散列函数为H（key）=key mod 13

12、，则它的开散列表中散列地址为1的链中的结点个数是（ ）A1 B.23 D.415设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（ ）A36，44，49，55，81，88 B.44，36，49，55，81，88C.44，36，49，81，55，88 D.44，36，49，55，88，8116在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_。17每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储

13、结构称为_。18在顺序表上读表元算法的时间复杂度为_。19双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：Snext=P;Sprior=Pprior;Pprior=S;_;20设数组A0.80.8的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素Aij的存储位置为a+66 L，则元素Aji的存储位置为_。21有4个结点且深度为4的二叉树的形态共有_种。22某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_。23第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一

14、个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_。24一个具有10个顶点的完全无向图中有_条边。25一棵平衡二叉树中任一结点的平衡因子只可能是_。26二分查找的时间复杂度为_。27二路归并排序算法的时间复杂度为_。28文件的基本存取单位是_。29有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push（a）表示a入栈，pop（a）表示a出栈）。30某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。31用冒泡排序算法对数据序列（49，38，65，

15、97，76，134，27，49）进行排序，写出整个冒泡排序的每一趟过程。32题32图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。33已知连通网的邻接矩阵A=， 试画出它所表示的连通网并画出该连通网的最小生成树。34设单链表的结点结构如下：struct nodedatatype data;struct node*next;试编写一个函数int count（struct node *head,datatype x）统计单链表中数据域为x的结点个数。35试写出直接插入排序算法。全国2006年1月高等教育自学考试数据结构导论试题1.数据结构中所定义的数据元素，是用于表示数

16、据的（）A.最小单位 B.最大单位C.基本单位 D.不可分割的单位2.数据的四种基本存储结构是指（）A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B顺序存储结构、索引存储结构、链式存储结构、散列存储结构C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构3.对于长度为n的顺序表执行删除操作，则其结点的移动次数（）A.最少为0，最多为n B.最少为1，最多为nC.最少为0，最多为n-1 D.最少为1，最多为n-14.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）next=q B. p-n

17、ext=q-nextC. p=q-next D. p-5.有关栈的描述，正确的是（）A.栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作6.二维数组A1020采用按行为主序的存储方式，每个元素占4个存储单元，若A00的存储地址为300，则A1010的地址为（）A.700 B.1120C.1180 D.11407.关于二叉树性质的描述，正确的是（）A.二叉树结点的个数可以为0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别为

18、左、右孩子8.具有4个结点的二叉树可有（）A.4种形态 B.7种形态C.10种形态 D.11种形态9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）A.先根遍历 B.中根遍历C.后根遍历 D.层次遍历10.具有n个顶点的无向图，若要连通全部顶点，至少需要（）A.（n-1）条边 B. n条边C. n（n-1）条边 D. n（n-1）/2条边11.下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A.集合 B.线性结构C.树形结构 D.图形结构12.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A.同义词之间发生冲突引起的B.非同义词之间发生冲突引起的C.同义

19、词与非同义词之间发生冲突引起的D.散列地址“溢出”引起的13.ISAM文件组织方式是一种（）A.专门适用于磁带的存取方法B.专门适用于磁盘的存取方法C.专门适用于光盘的存取方法D.可适用于磁带、磁盘、光盘等多用途的存取方法14.当待排序序列中记录数较多时，速度最快的排序方法是（）A.冒泡排序法 B.快速排序法C.堆排序法 D.归并排序法15.若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（）A.15，22，26，30，50，53，69，87 B.15，30，22，26，50，69，53，87C.15，26，30，22，50，69，53

20、，87 D.15，26，22，30，50，53，69，8716.数据表示和_是程序设计者所要考虑的两项基本任务。17.一个算法通常可从正确性、易读性、健壮性和_等四个方面评价、分析。18.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为_。19.串是一种特殊的线性表，串常见的存储结构有顺序存储和_两种方式。20.我们通常把队列中允许插入的一端称为_。21.二维数组在机器级的具体实现，通常均采用_存储结构。22.深度为k的满二叉树其叶子结点个数共有_个。23.二叉树通常采用_两种存储结构表示。24.若一个完全无向图具有n条边，则该图的顶点个数为_。25.查找表的逻辑组织结构实

21、际上是_结构。26.对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为_。27.若构成索引文件的索引表有序而主文件无序，则该索引文件称为_文件。28.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行_趟起泡。29.试采用类C语言，给出二叉树的二叉链表结构描述。30.试用Prim算法构造题30图的最小生成树，要求分步给出构造过程。题30图31.请按照数列28，45，33，12，37，20，18，55的先后插入次序，生成一棵二叉排序树。32.已知一组键值序列（33，37，26，43，55，67，42，38），试采用堆排序法对该组序列作升序排序，给出建立的初始堆，以及第一次输出堆元

22、素后筛选调整的堆。33.已知一组键值序列（22，24，26，25，27，29，21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。四、设计题（本大题共2小题，每小题7分，共14分）34.试编写一个函数，以读取单链表的第i个元素。35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述。全国2005年10月高等教育自学考试数据结构导论试题1.若要描述数据处理的变化过程，其正确的次序应为（ ）A.处理要求、基本运算和运算、算法B.处理要求、算法、基本运算和运算C.基本运算和运算、处理要求、算法D.算法、处理要求、基本运算和运算2.从运算类型角度考虑，属于引用型的运算

23、是（ ）A.插入、删除 B.删除、修改C.查找、读取 D.查找、删除3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数（ ）A.最少为0，最多为n B.最少为1，最多为nC.最少为0，最多为n+1 D.最少为1，最多为n+14.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是（ ）A.s-next=q；next=s-B.p-next=sC.s-next；D.s-5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为（ ）A.5、6、7、8 B.8、7、6、5C.8、7、5、6 D.5、6、8、76.FORTRAN语言对数组元素的存放方式通

24、常采用（ ）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个顶点的有向完全图应具有（ ）A.20条弧 B.50条弧C.90条弧 D.100条弧10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为（ ）A.V1V2V3V

25、5V4V6B.V1V2V3V5V6V4C.V1V5V2V3V6V4D.V1V3V6V4V5V211.适用于静态的查找方法为（ ）A.二分查找、二叉排序树查找B.二分查找、索引顺序表查找C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找12.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应（ ）A.从MID/2位置开始 B.从MID位置开始C.从MID-1位置开始 D.从MID+1位置开始13.磁盘是一种广泛使用的外部存储设备，对磁盘的存取操作（ ）A.只能用顺序方式 B.只能用随机方式C.既能用顺序方式也能

26、用随机方式 D.方式取决于具体的机器14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为（ ）A.直接插入排序法 B.快速排序法C.堆排序法 D.归并排序法15.若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是（ ）A.插入排序 B.冒泡排序C.快速排序 D.选择排序16.算法通常可分为程序、伪语言算法和_三种类型。17.时间复杂性描述量级中，若某算法达到_量级，则该算法通常是不可计算的。18.对顺序表执行删除操作，其删除算法的平均时间复杂性为_。19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示