计算机软件基础复习提纲

1 一 填空题 1 程序设计的关键在于设计出一个好的算法 2 数据 数据节点和数据项构成了数据组织的三个层次 其中数据项 是具有独立含义的最小标 识单位 3 数据的逻辑结构和物理结构之间的相互运算是通过算法 来实现的 4 所有节点按 1 对 1 的邻接关系构成的整体就是线性 结构 5 表长为 0 的线性表称为 空 表 6 直接插入排序最好情况的时间复杂度为 O n 7 程序段 i l while i n i i 2 的时间复杂度为 O log2n 8 c 语言属于计算机高级语言 既可以用来写系统软件 也可以用来写应用软件 9 算法是有穷的 而程序可以是 无穷的 10 实型常量在一般微型机中占用 4 个字节 11 char 型和 int 型的运算结果为 int 型 12 Getchar 和 putchar 函数只能输入 输出 1 个字符 13 源程序必须翻译成机器指令即机器语言 这一工作由编译系统 来完成 14 字符串的长度为串中字符的个数 但在内存中所占的字节数应比长度多 1 15 执行 a 3 b 4 a a b b a b 后 则 a 和 b 的值分别为 7 和 11 16 对于 scanf 2d 3d 4d 2 回车 7 下列程序段 int i j 10 printf 2 下列程序运行后的输出结果是 1 6 inlcude Main int a l 2 3 4 5 6 p p a p 3 2 printf d d n p p 3 3 下列程序运行后的输出结果是 s 55 inlcude Main int S i l sum for i 10 i s sum i printf S d n s sum int k int x 0 return x k 4 下列程序运行后的输出结果是 abcd main char sl abcdABCD s2 10 int k 0 j 0 while s l k A s2 j s 1 k s2 j 0 printf s n s2 5 下列程序运行后的输出结果是 DCBAEF void fun char pl int n chart p2 p2 pl n 1 while p110 break else continue printf d n x 7 下列程序运行后的输出结果是 6 int b l int f int a b a return b main int a 2 b 3 a f 8 下列程序运行后的输出结果是 23 Main int x 4 1 2 3 4 5 6 7 8 3 9 10 2 4 2 9 6 s 0 k 0 for knext NULL p p next j return j 10 下列程序运行后的输出结果是 1 6 3 2 3 include main int j 1 j 3 printf d i int i 0 I j 2 printf d d i j printf d d i j 11 下列程序运行后的输出结果是 10 int f int n if n 1 return 1 8 else return f n 1 1 main int i j 0 for i 1 inext while p NULL Push p p next p head next while EmptyStaek 五 程序填空题 1 下面程序是从输入 3 个数中找出最大数 并输出最大数 int max intx int y int z int t t x y x y retum t z t z main int a b c scanf d d d p r j r j r j 1 r j 1 p if flag return 3 下列程序的功能是将输入的 10 个整型数存入一维数组中 并求其中所有素数之和并输出 main int x 10 9 sum 0 flag k j for k 0 k 10 k scanf d else sq front sq front 1 maxsize x sq data sq front Return 1 6 以下运算实现在链队上的入队列 请在 处用适当的语句予以填充 void EnQueue Queptr Tp lq data Type x LqueueTp p p Lqueue Tp malloc sizeof Lqueue Tp p data x p next NULL 1q rear next p lq rear p 六 编程题 1 输入一个长整型正整数 将其转换成对应八进制整数的字符串 然后输出该字符串 要求 用指向字符串的指针变量来处理求出的八进制数字字符 解 10 main char s 10 p long x int y p s 8 p 1 0 scanf ld x x 8 P Printf s n p 2 以二叉链表作为存储结构 用类 C 语言编写求二叉树中叶子数的算法 解 先求左子树的叶子数 再求右子树的叶子数 两者相加就是根结点叶子数 也就是对应二 叉树的叶子数 Int leafcount bitreptr T if T NULL leaf 0 e