湖南人文科技学院 数据结构测试卷





课教师 学号 姓名
湖南文科技学院 通控系 通信工程专业2009级
20102011 学年第 二 学期 数结构 课程考核试卷(A)
考核方式 （闭卷) 考试时量：120 分钟
题 号

二
三
四
总分
合分
复查
实分









评卷



填空题：（空1 分 20 分）

1数结构形式定义（D R）中D 限集合RD 限集合
2算法效率分 效率 效率
3n结点单链表中查找某数时间复杂度_______________n结点序表存储时查找某数时间复杂度_______________
4循环队列中队首指针指队首元素 位置
5具n单元循环队列中队列满时 元素
6设串tI am a student good串SubSubstring(t87)Sub __________
7假设二维数组A6×8元素相邻6字节存储存储器字节编址已知A[0][0]存储位置1000行优先存储A[3][4]址 列优先存储时A[3][4]址
8设棵完全二叉树中21结点果左右序1开始序编号编号8双亲结点编号___________编号8左孩子结点编号_____________
9解决计算机机印机间速度匹配时通常设置印数缓区机输出数次写入该缓区印机该缓区中取出数印该缓区应该_________ 结构特点__________
10算法指令限序列中条指令表示操作外算法具五重特性分 __________________________________ 零输入输出
11稀疏矩阵中非零元素应三元组包括该元素_______________________________ 三项
分
评卷



二选择题：（空2分30分）
7 页第 1 页
1．（ ）具相特性数元素集合数子集
A数符号 B数象 C数 D数结构
2．链表表示线性表优点 ( )
A便机存取 B花费存储空间序表少
C便插入删 D数元素物理序逻辑序相
3．堆栈输入序列（ABCD）输出（ ）
A(ABCD) B (DCBA) C (ACDB) D (CABD)
4．数组表示循环队列中frontrear分队列头尾指针maxSize数组长度队满条件( )
A frontmaxSize B (rear+1)maxSizefront
C rearmaxSize D rearfront
5．设称矩阵A采压缩存储方式行序序存储a11第元素存储址1元素占址空间 a85址（ ）
A 23 B 33 C 18 D 40
6．已知棵二叉树先序序列ABCDEFG中序序列CBDAEGF序序列( )
A CDBGFEA B CDBFGEA C CDBAGFE D BCDAGFE
7．采折半查找方法进行查找数文件应（ ）限（ ）
A序表 序存储结构 B序表 链式存储结构
C机表 序存储结构 D机表 链式存储结构
8．执行面程序段时执行S语句次数（ ）
for(int I1Ifor(int j1jS
A n2 B n22 C n(n+1) D n(n+1)2
9．串种特殊线性表特殊性体现（ ）
A 序存储 B 数元素字符
C 链接存储 D 数元素字符
10．五分带权值923514叶子结点构成棵哈夫曼树该树带权路径长度( )
A 60 B 66 C 67 D 50
7 页第 2 页
11．深度5二叉树( )结点
A．10 B．16 C．31 D．32
12 数组逻辑结构列（ ）逻辑结构
   A．线性表       B 栈      C 队列    D　树
13．设指针变量p指单链表结点A删结点A继结点B需操作（ ）
   A p>nextp>next>next      B pp>next      
   C pp>next>next             D p>nextp
1410阶称矩阵压缩存储维数组A中数组A长度少（  ）
   A 100       B 40        C 55      D 80
15．设结点A3兄弟结点结点B结点A双亲结点结点B度数数（ ）
   A 3         B 4        C 5     D 1

分
评卷
三判断题（题1分10分）


1．三结点二叉树三结点树样具三种形态 （ ）
2．算法没输入必须输出 （ ）
3．链表进行插入删操作时必移动链表中结点 （ ）
4．子串ABC串AABCABCD中位置2 （ ）
5．入栈操作入队列操作链式存储结构实现时需考虑栈溢出情况 （ ）
6．序表查找指序存储结构进行查找 （ ）
7．列插入删操作分表两端进行线性表种先进出结构 （ ）
8 线性表序存储时逻辑相邻元素必存储物理位置次序相邻（ ）
9．链表删算法简单删链中某结点计算机会动续单元前移动 （ ）
10 二叉树中叶子结点二叉树中没左右子树结点 （ ）

分
评卷
四程序题（12题题5分34题题6分56题题9分40分）


1． 写出程序段功果输入数254写出输出结果(5分)
7 页第 3 页
void conversion()
{
Stack s
int n
SElemType e
initstack(s)
printf(Please input number)
scanf(d&n)
while(n)
{
push(sn9)
nn9
}
while(stackempty(s))
{
pop(se)
printf(de)
}
}
该程序功：


输入254输出数：

2读函数指出函数功(5分)
LinkList mynote(LinkList L)
{ L带头结点单链表头指针
if(L&&L>next)
{
qLLL－>nextpL
S1： while(p－>next) pp－>next
S2： p－>nextqq－>nextNULL
}
7 页第 4 页
return L
}
请回答列问题：
（1）说明语句S1功

（2）说明语句组S2功

（3）设链表表示线性表（a1a2 …an）写出算法执行返回值表示线性表
3请标号处填写合适语句完成列程序(空2分6分)
int Binary_Search(SStable STKeyType key)
{ * 关键字升序排列表ST中查找关键字key数元素找返回该元素表中位置否返回0 *
int midlowhigh
low1highlength
while(low{ * 非空进行较测试 *
mid ⑴
if(keyelse if(key>STelem[mid]key) ⑶
else return mid
}
return 0
}
⑴ ⑵ ⑶

4 指出面函数f功返回值含义(6分)
int f(char s1[]char s2[])
{
   int i0j0
7 页第 5 页
  while(s1[i]&&s2[j])
{
   if(s1[i]>s2[j])     
return 1
   else if(s1[i] return 1
   else i++j++
}
if(s1[i])
    return 1
else if(s2[j])
    return 1
else return 0
}
函数f功：

返回值1含义：
返回值0含义：
返回值1含义：
5．设计判断单链表中元素否递增算法(9分)
结点定义：
typedef struct Lnode
{
int date
struct Lnode *next
}LNode*Link
函数定义：BOOL InSort（Link head）
head链表头结点头结点中存数升序排列返回true否返回false果headNULL者链表结点返回true写出该函数函数体
BOOL InSort（Link head）
{

7 页第 6 页










}

6．写出链栈中数出栈函数(9分)
堆栈中结点定义：
tyedef struct Stack
{
char date
struct Stack *next
}*LinkStack
出栈函数定义：void Pop（LinkStack head） head栈顶指针
Void Pop（LinkStack head）
{











}
7 页第 7 页
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档