文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 西南财经大学天府学院试卷(a卷)

西南财经大学天府学院试卷(a卷)

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
路漫漫其修远兮，吾将上下而求索-百度文库

西南财经大学天府学院试卷(A卷

考试科目：数据结构_本
年级层次
教学班
姓名：学号：
试题号一二三四五六总分记
分考分表阅卷人
注意：
1、本次考试为A卷考试，考试时间120分钟。2、请将答案依次写在专用答题纸上。3、全卷共一部分，满分为100分。
一、单项选择题（共15题，每题2分，共计30分）1、算法指的是（）。
A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列
2、若进栈序列为1、2、3、4、5，若允许出栈操作可以在任意可能的时刻进行，则以下不可能的出栈序列是（）。
A、3、4、2、5、1B、2、5、4、1、3C、2、3、1、5、4D、3、5、4、2、13、在一个长度为n的顺序表中向第i个元素(0之前插入一个新元素时，需要向后移动（）个元素。A、n-iB、n-i+1C、n-i-1D、i
4、假定一个链表队列的队首和队尾指针分别用front和rear表示，每个结点的结构为：datanext当出队时所进行的指针操作为（）A、front=front–>nextB、rear=rear–>nextC、front–>next=rear;rear=rear–>nextD、front=front–>next;front–>next=rear5、向一个栈顶指针为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、对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数为（）。A、2B、3C、4D、57、线索二叉树中，结点p没有左子数的充要条件是（）。
A、p->lc=NULLB、p->ltag=1C、p->lc=NULL且p->ltag=1D、以上都不对
8、若根据查找表（23，44，36，48，52，73，64，58）建立哈希表，采用h(K=K%7计算哈希地址，则哈希地址等于3的元素个数为（）。A、1B、2C、3D、49、若一个元素序列基本有序，则选用（）方法较快。
A、直接插入排序B、简单选择排序C、堆排序D、快速排序10、线性表采用链式存储时，其元素地址（）。
A、必须是连续的B、一定是不连续的C、部分地址是连续的D、连续与否均可11、对一组数据（86，48，26，15，23）排序，数据的排列次序在排序过程中的变化为：①8648261523②1548268623
③1523268648④1523264886
这个排序过程采用的排序方法是（）。
11

路漫漫其修远兮，吾将上下而求索-百度文库

A、冒泡B、选择C、快速D、插入12、在数据结构中，从逻辑上可以把数据结构分为（）。A．动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
13、已知函数SubString(s,i,j的功能是返回串s中从第i个字符起长度为j的子串，函数SCopy(s,t的功能为复制串t到s。若字符串S=”SCIENCESTUDY”，则调用函数SCopy(P,Sub(S,1,7后得到（）。
A、P=”SCIENCE”B、P=”STUDY”C、S=”SCIENCE”D、S=”STUDY”14、若将一个10×10阶的对称矩阵压缩存储到一个一维数组中，则该一维数组的大小应该是（）。
A、55B、56C、45D、4615、根据堆定义，下面的4个序列中，（）是堆。A、75，65，30，15，25，45，20，10B、75，65，45，10，30，25，20，15C、75，45，65，30，15，25，20，10D、75，45，65，10，25，30，20，15

二、是非题（下列叙述正确的写上T，否则，写上F。共10题，每题1分，共计10分）
1、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。
（）
2、线性表中的每个结点最多只有一个前驱和一个后继。（）3、线性表简称为“顺序表”。（）
4、线性的数据结构可以顺序存储，也可以链式存储。非线性的数据结构只能连接存储。（）5、从单链表的任一结点出发，都能访问到所有结点。（）6、满二叉树一定是完全二叉树。（）
7、在有向图G中，和是两条不同的边。（）
8、在有序的顺序表和有序的链表上，均可使用折半查找来提高查找效率。（）9、若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定是任何结点都没有右子树。（）10、如果某种排序方法是不稳定的，那么该排序方法不具有实用价值。（）
三、填空题（共10空，每空1分，共计10分）
1、每次从无序表中顺序取出一个元素，把这个元素插入到有序表中的适当位置，此种排序方法叫做【1】排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做【2】排序。
2、如果经常对线性表进行插入和删除运算，则最好采用【3】存储结构。
3、数据结构按结点间的关系，可分为4中逻辑结构，它们分别是【4】、【5】、【6】和【7】。
4、假定一个顺序循环队列的存储空间长度为QueueSize，队首和队尾指针分别用front和rear表示，如果采用少用一个存储空间的方式来区分循环队列是队空还是队满，则判断队空的条件是【8】；判断队满的条件是【9】。
5、已知二维数组A[5][3]，其每个元素占2个存储单元，并且A[0][0]的存储地址为1000。则元素A[3][2]的存储地址为【10】。
四、算法填空题（每空2分，共20分）
1、下列算法片段是矩阵快速转置算法，请在划线的位置填入适当的内容。#defineARRAYSIZE1024typedefstruct{introw,col;/*非零元素的行号和列号*/DataTypevalue;/*非零元素的值*/
}TriType;typedefstruct{triTypeitems[ARRAYSIZE+1];/*非零元三元组，item[0]未用*/
22

路漫漫其修远兮，吾将上下而求索-百度文库

introws,cols;/*稀疏矩阵的行数、列数*/intnums;/*稀疏矩阵的非零元素个数*/}TriArray;FastTransMatrix(TriArrayTA,TriArrayTB
{/*TA为转置前的三元组属性表，TB为转置后的三元组顺序表*/inti,j=0,k=0;intpos[ARRATSIZE+1],num[ARRATSIZE+1];if(TA.nums{
for(i=1;i<=TA.cols;i++num[i]=0;for(i=1;i<=TA.nums;i++/*求TA中每一列非零元个数*/【1】;pos[1]=1;for(i=2;i<=TA.cols;i++/*计算第i列第一个非零元的位置【2】;
for(i=1;i<=TA.nums;i++{j=TA.items[i].col;k=pos[j];TB.items[k].row=TA.items[i].col;TB.items[k].col=TA.item[i].row;
TB.items[k].value=TA.items[i].value;【3】;}}
TB.rows=TA.cols;TB.cols=TA.rows;}
2、下列算法片段预实现的功能是：对有序表ST进行折半查找，成功时返回记录在表中的位置，失败时返回0。请在划线的位置填入适当的内容。typedefstruct{keytypekey;}ElemType；
typedefstruct{ElemType*elem;/*数据元素存储空间基址，建表时按实际长度分配，0号空间留空*/intlength;/*表长度*/
}SSTable;
intSearch_Bin(SSTableST,keytypekey{/*在表R中查找关键字k*/
intlow=1,high=ST.length;
while(【4】{
mid=(low+high/2;
if(key=ST.elem[mid].keyreturn【5】;/*找到待查元素*/elseif(key>ST.elem[mid].key【6】;/*继续在前一半查找*/else【7】;/*继续在后一半查找*/}
return0;/*顺序表中不存在待查元素*/
}

33

路漫漫其修远兮，吾将上下而求索-百度文库

3、下列算法片段是直接插入排序算法。请在划线的位置填入适当的内容。voidInsertSort(SqListL
{/*对顺序表L作直接插入排序for(i=2;i<=L.length;i++if(L.r[i].key/*若<,则将L.r[i]插入有序子表*/{L.r[0]=L.r[i];/*复制为哨兵*/
【8】;
for(j=i-2;【9】;j--L.r[j+1]=L.r[j];/*记录后移*/
【10】;/*插入到正确位置*/
}}
五、算法应用题（共15分）1、模式匹配的KMP算法应用
设目标为s=”abcaabbabcabaacbacba”，模式p=”abcabaa”。(1计算模式p的next[j]函数值。（3分）
(2不写出KMP算法，只画出采用next[j]函数进行模式匹配时每一趟的匹配过程。（2分）2、若一棵二叉树后序遍历为DHEBFIGCA，中序遍历序列为DBEHAFCIG。试画出这棵二叉树。（5分）
3、对于给定的一组记录的关键字{23，13，17，21，30，60，58，28，30，90}。试写出采用冒泡排序和快速排序方法时，每一趟排序后的结果。（10分）
六、算法设计题（共10分）
已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。


44

本文来源：https://www.2haoxitong.net/k/doc/e1de703ff41fb7360b4c2e3f5727a5e9856a27b2.html

《西南财经大学天府学院试卷(a卷).doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

2021入党谈话记录范文 2021入党谈话记录范文 2021入党谈话记录范文 年立冬健康养生- 2020遵义中考录取分数线介绍- 2019年考研英语试题与答案解析(完整版) 考研英语：新题型之七选五题解题攻略 (完整版)2019考研英语(一)真题答案(完整版) 2018新课标全国卷3高考理科数学试题及答案解析- 小学师徒结对活动记录文本表
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号