西南交通大学赵宏宇老师数据结构套题及其答案，可用作平时作业参考及考试复习，绝对真实，独家资源
西南交通大学赵宏宇老师数据结构套题及其答案，可用作平时作业参考及考试复习，绝对真实，独家资源
2021-11-27 17:39:49
264KB
1
西南交大;西南交通大学;数据结构;赵宏宇;（C语言版）数据结构习题集(严蔚敏，吴伟明)
• 绪论
1.8，1.9，1.12，1.20
• 线性表
2.19, 2.20, 2.21 (电子教案例5)
2. 24
2.31, 2.32
2021-11-18 14:03:34
31KB
西南交大;西南交通大学;数据结构;赵宏宇;• 栈与队列
3.24 3.25
3.27* (选做)
编程作业
1. 输入一个非零正整数，输出其各位数字。要求数字之间间隔至少一个空格。
例如：输入12085, 输出为1 2 0 8 5。
要求：采用递归和非递归(用堆栈)两种算法；输入的整数不允许按单个字符输入。
2. 八皇后问题是一个古老而著名的问题。该问题要求在88格的国际象棋盘上摆放着8个皇后，使其不能互相攻击（如下图所示）。即任意两个皇后都不处于同一行、同一列或同一斜线上。问有多少种摆法。著名数学家高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的方案。后来有人用图论的方法解出有92种方案。现在用计算机递归程序，可以很方便地求出这92种方案。请设置堆栈，消除下面递归程序的递归。
2021-11-18 14:03:34
55KB
西南交大;西南交通大学;数据结构;赵宏宇;1. 写算法
(1) 已知二叉树（二叉链表）根结点指针为bt，求该二叉树中的叶子数目。
(2) 已知某二叉树（三叉链表）的根结点地址root，该树中各结点的左、右儿子指针域已正确填充，写一个算法将所有结点的双亲指针域正确填充。
(3) 已知某二叉树（二叉链表）的根结点指针bt。编写算法，将该二叉树中所有结点的左右子树互换。
(4) 已知n个结点的完全二叉树结点数据域值按结点编号次序顺序存于一维数组（元素下标范围0..n-1）。编写算法，由该数组首地址以及数组长度n建立对应的二叉链表存储结构。
2. 上机题
(1) 编写完整程序，用先序遍历法建立二叉树的二叉链表存储结构，要求结点data域值类型为int。输入的先序遍历整数序列用0表示NULL指针域，其它有效结点的data域值均不等0。定义三个算法函数，分别计算并输出二叉树中结点data域值的最大值、结点data域值之和以及data域值小于0的结点数。
(2) 从键盘输入n个数据建立n元完全二叉树顺序存储结构。实现该完全二叉树的先、中、后序遍历。
2021-11-18 14:03:34
389KB
西南交大;西南交通大学;数据结构;赵宏宇;一、二叉树（二）
1. 写算法
(1) 二叉树的直径定义为从根结点至叶子的最大路径长度。编写算法，求二叉树(二叉链表)的直径。
(2) 已知二叉树(二叉链表)根结点指针bt，树中两个结点的指针p、q。编写算法求距离结点*p和*q最近的公共祖先的地址。
(3) 已知二叉树(二叉链表)根结点指针bt，利用二叉树叶子结点的rchild指针域将所有叶子结点从左向右连接成一个单向链表。算法返回单向链表头结点指针(即最左边第1个叶子结点的地址)。
2. 编程题
(1) 从键盘输入一个字符串（要求字符串中无重复字符），将串中字符当做完全二叉树的顺序存储结构，建立对应的完全二叉树的二叉链表存储结构，输出先、中、后序遍历结果。
(2) 用先序遍历法建立二叉树二叉链表存储结构(结点数据域类型为char，输入字符序列用字符'#'表示NULL)，实现中序线索化，并用非递归算法输出中序遍历结果的正序和逆序序列。
二、图
1. 已知某无向图如下图所示。画出该图的多重邻接表存储结构示意图。根据该存储结构，写出从顶点v0出发，深度和宽度优先遍历顶点访问次序。
2. 写一个算法，判断无向图是否有环。算法提要：深度优先遍历过程中，访问某顶点后，该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边)，则有环。
3. 编程题: 建立无向图邻接表存储结构，输出深度和宽度优先遍历顶点访问次序。
4. 编程题：建立AOE网络存储结构，计算并输出ve[]和vl[]。
5. 选作题*：算法设计-已知AOE网络的邻接表存储结构G，ve[]和vl[]值已全部求取，写出算法，输出所有关键路径。要求每条关键路径用源点至汇点的顶点序列（拓扑有序）表示。
2021-11-18 14:03:33
258KB
西南交大;西南交通大学;数据结构;赵宏宇;一、查找
1. 算法设计题 ：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，编写算法用对分查找求下标i，满足ai-1
2021-11-18 14:03:33
1.68MB
西南交通大学;实验(大作业)题目：C语言文件操作;实验目的：
(1) 掌握C语言字符文件读写方法；
(2) 掌握C语言二进制文件读写方法。
实验要求：
(1) 完成2个文件操作程序。
(2) 撰写实验报告：每个程序包括源程序代码；按要求描述关键算法或算法流程图；提供程序测试结果(至少两种不同输入，可屏幕截图)与结论。
实验内容：
1. 在字符文件b.txt中录入n个整数，录入整数的分隔符为空格、换行或TAB。若n=5，则b.txt的一种正确格式为
5
9 12 -15
30 -7
即b.txt的第一个数为n，后面是n个整数。
编写程序，从文件b.txt读出n值，建立长度为n的动态1维整型数组，然后继续从文件b.txt读入n个整数存于该数组，进行由小到大排序，最后将排序结果输出到字符文件c.txt中。
要求的输出格式是每个整数%6d，每输出5个整数换一行。
实验报告中要求给出该程序的流程图。
2. 1616点阵汉字的显示。从键盘输入一个汉字，从1616点阵汉字库文件HZK16.dat中毫读取汉字点阵信息，打印汉字到控制台屏幕上（构成汉字的每个点用输出字母O表示）。
输入输出示例：
请输入一个汉字:中
O
O
O O
OOOOOOOOOOOOOO
O O O
O O O
O O O
O O O
OOOOOOOOOOOOO
O O O
O
O
O
O
O
O
提示1：16*16点阵字库文件HZK16.dat的存储格式。
以汉字“我”为例，16*16点阵构成的字形信息用二进制编码（1表示有点，0表示无点）形成32字节，每行2个字节，共16行，如下所示。这32个字节在文件中的存储顺序为：每行从左向右，行从上到下。
16*16点阵字库文件HZK16.dat中，每个汉字（32字节字形信息）按区位码由小到大的顺序存储。以汉字“啊”为例，它的区号为16，位号为1，故它的32字节字形信息在文件中的起始字节偏移量offset=((区号-1)*94+位号-1)*32。
0000010010000000 0x04,0x80
0000111010100000 0x0E,0xA0
0111100010010000 0x78,0x90
0000100010010000 0x08,0x90
0000100010000100 0x08,0x84
1111111111111110 0xFF,0xFE
0000100010000000 0x08,0x80
0000100010010000 0x08,0x90
0000101010010000 0x0A,0x90
0000110001100000 0x0C,0x60
0001100001000000 0x18,0x40
0110100010100000 0x68,0xA0
0000100100100000 0x09,0x20
0000101000010100 0x0A,0x14
0010100000010100 0x28,0x14
0001000000001100 0x10,0x0C
提示2：GB2312-80汉字内码
GB2312-80共收录约6700多个汉字以及其它符号，用一个94行*94列的表格表示（最多可表示94*94个汉字和符号）。某个汉字所在的行号（从1开始）称为“区号”，列号（从1开始）称为“位号”，形成区位码。
如：汉字“啊”在16行，第1列，故它的区位码为(16,1)。
在存储器中，为了与ASCII码区别，用内码表示一个汉字的编码，汉字的内码为一个2字节编码，第一字节=区号+160，第2字节=位号+160，故汉字“啊”的内码为(176,161)。
已知汉字内码，则在HZK16.dat中该汉字32字节字形信息首字节的存储位置为
offset=((内码第一字节-161)*94+(内码第二节字-161))*32
2021-11-18 14:03:32
360KB